2.1.1 数组

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

1.数组的基本特性

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

图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+树存储引擎中一个节点的多个孩子节点通过数组存储，在操作时始终保持该数组有序，同时叶子节点采用固定大小的数组来保存原始数据。当查找、更新、删除某个元素时，会按照根节点→分支节点→叶子节点的顺序查找，并利用有序数组的二分查找加快查找过程。当查找到达叶子节点时，表示已经定位到了待查询的数据信息。该信息中至少记录了当前待查找的数据在叶子节点的起始位置与长度。获取待查询的原始数据时，通常是通过数组的下标来得到的。