2.1 基础数据结构

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

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