2.1 基础数据结构

数组和链表的特性是互补的，其他数据结构基本上都是由数组和链表至少一种构成的。比如，Hash表底层就是采用数组来实现的，当Hash表中存储的元素发生Hash冲突时，根据不同的处理策略又会结合为不同的数据结构。当采用开放地址法解决Hash冲突时，Hash表内部仍然只采用数组存储数据；而当采用链地址法时，Hash表会将发生Hash冲突的元素用链表连接在一起，结合数组和链表来解决Hash冲突问题。再如，二叉树、红黑树可以看作具有两个指针的链表结构，这种结构是链表的一种进化版。跳表也是在链表基础上构建的一种高阶数据结构。B树、B+树则是包含多个链表指针的数据结构，在内部实现时通常将数组和链表二者结合使用。

综上，数组和链表在存储引擎甚至整个计算机中的重要性毋庸置疑。为方便后续内容的学习，本节将快速回顾一下数组和链表的核心内容。

2.1.1 数组

数组是大家平常接触最多也最熟悉的一种数据结构了，目前主流的编程语言基本上都提供数组直接使用。本小节从数组的基本特性、数组操作的时间复杂度、存储引擎中数组的适用场景进行分析。

1.数组的基本特性

数组是指在计算机内存中开辟一块指定大小的连续区域来存储相同类型的元素，其中内存起始地址为数组首地址。由于数组元素连续存储且类型相同，假设数组首地址为 A ，存储的元素大小为 M 字节，则数组中存储的第 i 个元素对应的地址为 A + i × M ，这意味着可以通过数组的下标在常数时间内访问数组中的任意一个元素，数组的这种特性称为顺序存储随机访问。此外，数组在使用上也比较简单。数组的简单示意如图2-1所示。

数组的缺点主要有以下几个。

❑ 大小固定： 数组在使用前初始化时需要分配空间，因此需要指定大小。如果存储的元素个数明确，则大小比较好确定；如果存储的元素是动态变化的，则比较难确定分配空间的大小，设置得太大容易造成空间浪费，设置得太小又会导致存储不下所有元素。鉴于原生的数组有这样的特点，一些编程语言对数组进行了封装，提供了动态数组的特性。比如Java语言中的ArrayList、C++中的vector等。在实际编程时会根据应用的实际情况动态地对数组的大小进行调整。

❑ 连续分配： 数组分配的空间是连续的，当数组规模太大并且连续的内存空间不够时会出现分配失败的情况。此外，连续分配的方式会使内存空间的利用率降低。

❑ 插入/删除慢： 在数组中，元素都是紧凑排列的。这也意味着，要在数组中插入或删除一个元素，操作的元素在数组中的位置就很重要。以插入元素为例，如果要在数组尾部插入一个元素，只需要给数组末尾的位置赋值即可。但如果要在数组的其他位置插入一个元素，则需要分为两个步骤：第一步，将插入位置及之后的数组元素依次往后移动一位，以便将当前待插入的数组位置空出来；第二步，对数组中待插入的位置进行赋值操作。尤其是在数组头部插入一个元素时，需要移动数组中的所有元素，这种情况下的开销还是比较大的。删除元素的过程和插入过程相反，当删除某个位置的元素时，需要将该位置之后的元素依次往前移动。

2.数组操作的时间复杂度

对于数据结构而言，主要功能体现在对数据结构的操作上，数组也不例外。下面将依次分析在数组中 插入、删除、查找 指定下标的元素对应的时间复杂度。

在数组中插入、删除元素的主要开销在于移动数组元素，不同位置移动的元素个数不同。通常数组的插入、删除的平均时间复杂度为 O （ N ），其中 N 为数组中元素的个数，而根据数组下标获取某个位置元素的时间复杂度则为 O （1）。

接下来思考一个问题：如果要查找某个元素是否存在于数组中，平均时间复杂度是多少呢？

要在一个数组中查找某个指定的元素，最直接的方式就是遍历一遍数组，然后逐个对比数组中的元素是否和查找的元素相等。在这个过程中，如果待查找的元素是数组中的第一个元素，则只需要遍历数组的第一个元素即可结束；而如果待查找的元素是数组中的最后一个元素或者数组中根本就不存在指定的元素，那么就需要遍历完数组中的所有元素后才能确定结果。所以查找的平均时间复杂度为 O （ N ），其中 N 为数组中元素的个数。

上述查找操作其实是一般意义上的查找，未考虑数组是否有序。对于一个有序的数组，在查找某个指定的元素时可以采用折半的思想进行优化。为了方便叙述，假设当前数组为Arr，数组长度为 N ，待查找元素为Target。具体过程为：首先根据数组大小计算出数组中间元素的下标mid（mid= N /2），然后比较当前查找元素Target和数组中间元素Arr[mid]，比较结果有如下三种可能。

❑ Target=Arr[mid] ：表示已经找到了待查找的元素Target，结束查找即可。

❑ Target < Arr[mid] ：表示当前查找的元素Target比数组中间的元素小，如果Target在数组中存在，则只可能位于数组[0，mid）这个下标区间内，故只需要在该区间继续进行递归查找。

❑ Target > Arr[mid] ：表示待查找的元素Target比当前数组中间元素Arr[mid]大，如果Target存在于数组中，只可能位于数组[mid+1， N ）这个下标区间内，故只需要在该区间按照上述过程进行递归查找。

综上，在有序数组中查找某个指定元素时，可以采用不断缩小数组查找区间的方式加快查找过程。由于每次比较都可以将数组的区间一分为二（缩小一半），因此该方法称为二分查找法或者折半查找法。这种查找方法查找的平均时间复杂度为 O （log N ）。

3.数组的适用场景

基于下标访问数组元素和有序数组的二分查找的时间复杂度都比较低，所以存储引擎使用数组时主要利用这两种方法。以B+树存储引擎为例，在B+树存储引擎中一个节点的多个孩子节点通过数组存储，在操作时始终保持该数组有序，同时叶子节点采用固定大小的数组来保存原始数据。当查找、更新、删除某个元素时，会按照根节点→分支节点→叶子节点的顺序查找，并利用有序数组的二分查找加快查找过程。当查找到达叶子节点时，表示已经定位到了待查询的数据信息。该信息中至少记录了当前待查找的数据在叶子节点的起始位置与长度。获取待查询的原始数据时，通常是通过数组的下标来得到的。

2.1.2 链表

数组会占用连续的内存空间，所以系统长时间运行后会使得内存空间的利用率降低，产生内存碎片，于是就有了链表。和数组一样，链表也是一种基础的数据结构。下面将从链表的基本特性、链表操作的时间复杂度、存储引擎中链表的适用场景几方面展开介绍。

1.链表的基本特性

链表不同于数组，在使用时既不需要指定大小，也不要求元素之间连续存储。链表以节点作为单位，一个链表通常由多个节点链接而成。链表中的每个节点内部除了维护存储的元素外，还需要额外维护指向下一个节点的指针结构。链表的示意如图2-2所示。

链表根据包含指针的个数不同，可以分为单链表和双链表。顾名思义，单链表只包含一个指针，它只能向后遍历。而双链表包含两个指针，所以可以向前和向后遍历。例如Java语言中的LinkedList、C++中的list等都属于双链表数据结构。

2.链表操作的时间复杂度

链表是链式存储、顺序访问，这也决定了链表操作的时间复杂度和数组截然不同。下面分析在链表中插入、删除、查找元素的时间复杂度。假设链表的元素个数为 N 。

如果插入和删除操作的元素位置是在链表的头部，则链表只需要重新设置指针指向即可，而不需要移动其他节点，因此时间复杂度为 O （1）。而如果是在链表尾部进行插入或删除操作则需要分两步：第一步，当链表只保存了头节点时，则需要先遍历到链表尾部，时间复杂度为 O （ N ）；第二步，当到达链表尾部后，进行真正的插入和删除操作，此时只需重新设置指针指向即可。在这种情况下，通常也可以通过额外保存一个链表的尾节点来避免遍历带来的开销。在保存头、尾节点的情况下，在尾部插入和删除的时间复杂度均为 O （1）。

在计算机中有一种针对有序链表进行优化的数据结构，它可以做到按照二分查找的思路查找元素，这种数据结构即为跳表，具体内容请参见2.3.3节。

3.链表的适用场景

链表不仅可以非常方便地在头部/尾部插入或删除元素，而且不要求所有元素连续存储，因此能更好地利用碎片内存空间。基于这些特性，链表在存储引擎中发挥着重要作用。以B+树存储引擎InnoDB为例，其内部就大量采用了链表结构，如采用链表对频繁插入或者删除的空闲页、脏页等进行管理。同时，InnoDB的叶子节点也采用了链表的方式，以方便进行数据的全表扫描。此外，部分场景还会通过链表来构建环形队列或者缓冲区等高阶的数据结构来存储数据。总之，只要对元素或数据进行频繁插入、删除的场景都可以优先考虑使用链表，因为它的效率极高。

基于数组下标访问元素比较快，但在空间上要求元素连续存储；而链表对元素的增删比较方便，同时不要求元素连续存储。可以说，数组和链表在很多特性上是相反的，二者是互补的关系。表2-1总结了数组和链表的几种操作的时间复杂度。