《数据库性能优化手册100技巧》pdf电子书免费下载
下载方式一：
百度网盘下载地址：https://pan.baidu.com/s/1BaYhXjfjqRHdtoCU7uMQSQ
百度网盘密码：1111
下载方式二：
http://ziliaoshare.cn/Download/af_124548_pd_SJKXNYHSC100JQ.zip
|
|
作者：empty 页数：230 出版社：empty |
《数据库性能优化手册100技巧》介绍
数组和链表是程序中常用的两种数据结构，也是面试中常考的面试题之一.然而对于很多人来说，只是模糊的记得二者的区别，可能还记得不一定对，井且每次到了面试的时候，都得把这些的概念拿出来背一遍才行，未免有些麻烦。而本文则会从执行过程图以及性能评测等方面入手，让你更加深入的理解和记忆二者的区别，有了这次深入的学习之后，相信会让你记忆深刻.数组在开始(性能评测)之前我们先来回顾一下，什么是数组?数组的定义如下：数组(Array) 是由相同类型的元素(element) 的集合所组成的数据结构， 分配一块连续的内存来存储。利用元素的索引(index) 可以计算出该元素对应的存储地址。最简单的数据结构类型是一维数组，例如，索引为0到9的32位整数数组，可作为在存储器地址2000，2004，2008，.2036中，存储10个变量，因此索引为i的元素即在存储器中的2000+4xi地址。数组第一个元素的存储器地址称为第一地址或基础地址。简单来说，数组就是由一块连续的内存组成的数据结构。这个概念中有一个关键词“连续 ，它反映了数组的一大特点，就是它必须是由一个连续的内存组成的。
数组的优点数组的“连续 特征决定了它的访问速度很快，因为它是连续存储的，所以这就决定了它的存储位置就是固定的，因此它的访问速度就很快。比如现在有10个房间是按照年龄顺序入住的，当我们知道第一房子住的是20岁的人之后，那么我们就知道了第二个房子是21岁的人，第五个房子是24岁的人.等等数组的缺点祸兮福所倚，福兮祸所伏。数组的连续性既有优点又有缺点，优点上面已经说了，而缺点它对内存的要求比较高，必须要找到一块连续的内存才行，数组的另一个缺点就是插入和删除的效率比较慢，假如我们在数组的非尾部插入或删除一个数据，那么就要移动之后的所有数据，这就会带来一定的性能开销，删除的过程如下图所示：数组还有一个缺点，它的大小固定，不能动态拓展。
链表链表是和数组互补的一种数据结构，它的定义如下：链表(LInkedlist) 是一种常见的基础数据结构， 是一种线性表， 但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer) 。由于不必须按顺序存储， 链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n) 的时间， 而顺序表相应的时间复杂度分别是O(logn) 和O(1) 。也就说链表是一个无需连续内存存储的数据结构，链表的元素有两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址。
单向链表单向链表中包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值，我们上面所展示的链表就是单向链表。双向链表双向链表也叫双链表，双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针，这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表，双向链表的结构如下图所示：区·12D·99·37·区循环链表循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。循环链表的结构如下图所示：
为什么会有单、双链表之分?有人可能会问，既然已经有单向链表了，那为什么还要双向链表呢?双向链表有什么优势呢?这个就要从链表的删除说起了，如果单向链表要删除元素的话，不但要找到删除的节点，还要找到删除节点的上一个节点(通常称之为前驱) ， 因为需要变更上一个节点中next的指针， 但又因为它是单向链表，所以在删除的节点中并没有存储上一个节点的相关信息，那么我们就需要再查询一遍链表以找到上一个节点，这样就带来了一定的性能问题，所以就有了双向链表。
链表优点链表的优点大致可分为以下三个：1.链表对内存的利用率比较高，无需连续的内存空间，即使有内存碎片，也不影响链表的创建；2.链表的插入和删除的速度很快，无需像数组一样需要移动大量的元素；3.链表大小不固定，可以很方便的进行动态扩展，链表缺点链表的主要缺点是不能随机查找，必须从第一个开始遍历，查找效率比较低，链表查询的时间复杂度是O(n)。性能评测了解了数组和链表的基础知识之后，接下来我们正式进入性能评测环节，在正式开始之前，我们先来明确一下测试目标，我们需要测试的点其实只有6个：·从头部/中间部分/尾部进行添加操作的性能测试；·从头部/中间部分/尾部开始查询的性能测试。因为添加操作和删除操作在执行时间层面基本是一致的，比如数组添加需要移动后面的元素，删除也同样是移动后面的元素；而链表也是如此，添加和删除都是改变自身和相连节点的信息，因此我们就把添加和删除的测试合二为一，用添加操作来进行测试。测试说明：1.在Java语言中， 数组的代表为ArrayList， 而链表的代表为LinkedList， 因此我们就用这两个对象来进行测试；2.本文我们将使用Oracle官方推荐JMH框架来进行测试， 点击查看更多关于JMH的内容；3.本文测试环境是JDK 1.8、MacMini、Idea 2020.1.1.头部添加性能测试