索引的存储结构

常见数据结构

  我们已经知道，索引是通过空间代价、写入更新维护代价来换取的高效率查询效能，那么在何种数据结构下，索引才能满足快速查询、数据变化后平衡的调整、对存储I/O友好的3种核心需求呢。我们可以把常见的数据结构类型列举进行探讨：

数据结构	缺陷表现	数据库场景致命伤	优点
链表	线性访问效率低，查找复杂度O(n)；插入/删除需遍历节点，效率不稳定	全表扫描性能极低，无法支持快速定位；内存或磁盘访问次数随数据量线性增长	结构简单，支持动态扩展；顺序插入效率高
哈希表	仅支持等值查询；哈希冲突可能引发链表退化；内存消耗大	范围查询失效（如BETWEEN、>）；相邻键值无关联，无法利用顺序性优化查询	等值查询O(1)；适合内存型存储引擎（如Memory引擎
二叉搜索树	极端情况退化为链表（如有序插入），查询复杂度O(n)；树高不可控	数据量增大时深度增加，IO次数激增；频繁磁盘访问导致性能骤降	结构简单，插入/删除逻辑清晰；理想情况下查询复杂度O(log n)
B树	非叶子节点存储数据，导致单个节点键值数量减少，树高较高；范围查询需跨层回溯	范围查询需多次跨节点跳转；数据分散存储，磁盘局部性差	多路平衡树减少IO次数；支持范围查询

  以上对比列表可以看到树的架构在数据检索以及写入更新维护中处于平衡状态，更适合索引，但是以上几种树结构均对于存储I/O不存在友好型。正是基于日益增长的数据量，以及业务查询性能和现有存储性能瓶颈的矛盾压力下，提出了更适合索引也是广泛沿用至今的数据结构B+树，他在二叉搜索树和B树的基础上演化而来，新增特点如下：

1. 高扇出性：非叶子节点不再存储数据，仅存储键值对、子树的最大值（或最小值、分割值）等必要信息，用于索引和导航（内部节点的键值信息存储在不同文档中存在不同的使用方法，本文后续采用存储分割值的思想进行描述和学习）；
2. 叶子链表：数据集中在叶子节点，叶子节点本身根据存储的数据关键信息大小自小而大、自大而小再次互相链接起来，形成有序双向链表。（如图5：一棵3阶B+树，内部节点存储的关键信息为分割值，即左指针指向的子树（或叶子节点）中数据均小于分割值，右指针指向的子树（或叶子节点）中的数据均大于等于分割值，叶子节点单向链表链接或者双向链表链接）

  非叶子节点不再存储数据，仅存储键值对用作导航后，可以让中间节点的空间利用率最大化，树的高度不用超过3层就可以容纳近亿级别的数据，节点大小还可以设计为数据页的大小以保证每次IO均是一个完整数据页信息，这样每个等值检索所需要的IO次数基本固定的，均是从根节点到中间节点，再到叶子节点的仅3次IO（实际环境中是根节点一般跟随字典常驻内存，这里仅作讨论）。
  而叶子节点的有序链表又使得在范围检索的场景下，只要找到了第一个符合条件的叶子节点，就可以正序或者反序进行批量数据扫描，减少中间节点回溯的这一步。
  这两个新的特性让他在存储I/O优化方面、范围扫描上比之B树更胜一筹。

B+树的检索过程

  为了方便理解B+树的检索过程，我们构造一个1到100的数值数据组成的5阶B+树作为例子（内部节点存储的关键信息为分割值），如图2.2所示。

等值检索

  假设我们需要定位数据中是否存在83的数字信息并在存在后提取对应数据位置出来，那么需要进行检索的路径如下：
  第一次IO读取根节点信息，从中得到的关键信息76和Max：100可以确认，下次需要从子树节点D中继续检索信息（如图2.3）。

  第二次IO读取节点D，从中得到关键信息81,86，所以确认下一次需要从81关键信息的右侧指针所指向的叶子节点处继续进行检索信息（如图2.4）。

  第三次IO，读取关键信息81右侧指针指向的叶子节点后，从中定位到83数据信息所在位置，完成数据检索定位(如图2.5)。

范围检索

  基于等值检索的例子，假设我们需要检索大于83的数据信息所在，并全部提取出来，那么检索路径将如何进行呢。这时候会有两条检索路径可以选择：
  路径一：在等值查询的基础上，通过3次IO定位到数值83所在叶子节点后，从叶子节点链表正序扫描下去，直到正序链表的底部，所有数据均是符合条件的（如图2.6）。

  路径二：存在两处指针起始，分别指向叶子链表最大键值所在叶子节点处和最小键值所在叶子节点处，如果存在统计信息的参考下，显然可以通过从最大键值所在叶子节点处的降序链表指针批量检索过去，直到检索到83数字所在叶子节点后，判断后续数据不再符合条件，停止数据检索过程（图2.7），显然路径二比路径一会少了3次IO过程。

B+树的写入更新

  原始数据总不会是一成不变的，在数据变化之后，索引里维护的数据也需要跟随着一起变化，那么B+树是如何进行插入、更新维护的呢。
  如下图2.8我们先构造一个数据为3,12,24,37,45,53,61,70,90,100的3阶B+树，然后顺序插入8，10，66的数据，来观察B+树的变化：

插入数据8的过程

  插入数据8：通过根节点、关键信息12的二层节点，定位到最左侧的叶子节点后，数据8插入叶子节点中，插入后各节点均满足（m阶树中节点中键值信息个数需要满足小于等于m-1）小于等于2的键值个数要求，B+树无需分裂，最后如下图2.9。

插入数据10的过程

  插入数据10：依然是通过根节点、关键信息12的二层节点，定位到最左侧的叶子节点后，插入数据10，插入后该叶子节点无法满足小于等于2的键值个数要求：

  于是开始进行分裂，把中间数据8更新到父亲节点中键值信息去，分裂一课子树出来，并生成新的叶子节点存放数据8和10，此时所有节点满足3阶B+树要求，停止数据插入，B+树如下图2.11：

插入数据66的过程

  插入数据66：通过根节点、关键信息61、90所在的二层节点，定位到61、70所在的叶子节点后，插入数据66，插入后该叶子节点无法满足小于等于2的键值个数要求：

  于是开始进行分裂，把中间键值数据66更新到父亲节点中键值信息去，分裂一课子树出来，并生成新的叶子节点存放数据66和70：

  但是这次分裂后也造成父亲节点也无法满足小于3的键值个数要求，于是进一步分裂二层节点，中间键值数据66继续往上一层更新到根节点中去，此二层节点分裂成两个二层节点：

  二层节点分裂，键值信息更新到根节点后，导致根节点也无法满足3阶树的要求，于是根节点需要做进一步分裂，变化成3阶4层B+树，此时所有节点满足3阶B+树要求，停止变化，插入数据过程结束，至此3阶B+树已经分裂成如下图2.15：

B+树的删除

  B+树的删除操作这是包含了检索定位过程，然后才是删除叶子节点中数据过程，继续以上面数据插入后的图2.15中最后的B+树图为例，我们针对其中的数据61进行删除演示：
  首先通过根节点、二层节点、三层节点导航定位到数据61所在叶子节点处，如图2.16

  然后进行数据删除操作，删除之后可以发现该叶子节点以及父亲节点中键值信息已经少于节点利用率50%，甚至为0，如图2.17：

  为保证B+树的平衡性，需要针对三层节点和其兄弟节点进行合并，合并后B+树如下图2.18：

  可以看到受到影响二层节点利用率也出现了低于阈值的现象，于是进一步合并二层节点，最终B+树层次降低，最后形成如下图2.19：

B+树分裂的性能影响

  在通过低阶B+树的插入、删除演示过程，我们知道为了保持B+树的平衡性和高效性的核心机制，B+树在某些场景条件下需要进行分裂操作，而分裂可能导致多次磁盘写入（原节点、新节点、父节点更新），显著增加I/O延迟。
  分裂操作期间还需要叶子节点所在的独占锁（如写锁），导致其他操作（如查询或插入）被阻塞，如果父节点也在更新时触发了分裂，可能引发多级锁竞争，进一步加剧响应延迟。
  所以在数据库索引设计中，应尽可能的去避免发生分裂所带来的性能影响，而优化的手段如下：

1. 延迟分裂（Lazy Splitting）：允许节点暂时超载，推迟分裂到后续操作中，减少高频小规模分裂的开销。
2. 批量插入（Bulk Insert）：对有序数据预分配节点，减少分裂次数。
3. 填充因子调优（Fill Factor）：降低节点初始填充率（如70%），预留空间以减少分裂频率。
4. 并发控制优化：使用无锁数据结构（如B-link树）或乐观锁机制，减少锁竞争。
   节点合并策略：在删除操作中合并节点时，避免过度合并导致后续插入频繁分裂。

3层B+树最多存储数据探讨

  我们学习了B+树的数据结构之后，会知道B+树非叶子节点的特性是不存实际数据，仅存储键值对和子树的最大值信息作导航索引用，这使得B+树只要阶数足够大的前提下，树的层次在3层以内就可以容纳绝大多数业务的数据，也能保证每次检索的最大IO次数不超过3次。
  那么B+树在3层时最多可以存储多少的数据呢。我们可以根据一些基础信息去评估一下这个数值，假设条件如下：

1. 根据达梦数据库中数据页大小的推荐值32KB，我们设定B+树的所有节点大小也为32KB，以符合1次IO得到1个完整数据页的需求；
2. 再次设定当前需要存储的索引数据是以bigint类型的键值数据，那么每条键值大小即为8B；
3. 叶子节点一般存储为所有数据信息，而实际环境中一般要考虑填充因子的因素，不可能整个数据页完全填充满，所以这里设定叶子节点尽可能使用数据页大小的一半左右，即16KB。
4. 64位操作系统下指针大小为固定值8B。

  于是我们得到了1个索引键值对大小占用为16B，而叶子节点键值对大小占用为24B（双链表），在此基础上，计算3层B+树大小最多容纳值过程如下：
  根结点（第一层）：最多可以存储的键值对数量为32768 / 16 ≈ 2048 个。
  中间节点（第二层）：每个中间节点最多也可以存储 32768 / 16 ≈ 2048 个键值对，于是根据根节点得到的子树数量，第二层最大键值对数量是：2048x2048≈4,194,304个。
  叶子节点（第三层）：每个叶子节点最多容纳键值对为
16384 / 24 ≈ 682个，那么总的叶子节点数量为 4,194,304 × 682 ≈ 2,860,515,328个键值对。
  通过以上的粗略计算评估，我们可以得出3层B+树大小最多存储的数据在2.8亿左右，当然这是粗略计算值，实际设计中不可能把根节点、第二层节点都完全填充满，存储的数据多少还是要和键值对的大小、数据行的大小、存储分布、填充因子等因素影响具体值相关联起来。
  但是我们仍然可以得出结论，3层的B+树几乎可以满足绝大部分业务的数据量了，而4层B+树虽说可以容纳更多的键值对上限，但是检索IO次数的增加也是制约着实际环境中设计使用的重点考量，通常会通过优化数据模型、分库分表等策略来避免4层B+树的出现。