B+树索引的基本原理

• 索引键：B+树索引的每个节点存储了数据表中一行或多行的索引键（即用于排序和查找的列的值）。
• 叶子节点：B+树的叶子节点包含了指向数据表中具体行的指针（或者直接包含行数据，取决于索引的实现方式），这些行的索引键值与叶子节点中的键相对应。
• 非叶子节点：B+树的非叶子节点（包括根节点）用于指导搜索查询向正确的叶子节点方向前进，但它们不包含行数据的直接引用。

例子：图书数据库的B+树索引

假设我们有一个图书数据库，其中的一个表格存储了图书信息，包括BookID（图书ID）、Title（标题）、Author（作者）等字段。我们决定对BookID字段创建一个B+树索引以加速基于图书ID的查询。

初始数据

假设表格中有以下图书ID：

• BookIDs: 1, 2, 3, 4, 5, 6, 7, 8

B+树索引结构

我们创建一个最大键数为3的B+树索引，对上述BookIDs建立索引。索引建立过程可能如下：

1. 插入键1到3：最初，根节点可以容纳3个键，所以当插入1, 2, 3时，它们都被存储在根节点。
2. 插入键4，节点分裂：插入键4时，根节点满了，需要分裂。根节点分裂成两个节点，键2提升为新的根节点键。现在，根节点包含键2，它有两个子节点：一个包含键1，另一个包含键3和4。
3. 继续插入键5到8：随着键5, 6, 7, 8的插入，树继续按需分裂，保持平衡。

使用B+树索引进行查询

现在，如果我们要查询BookID为6的图书信息，查询操作将遵循以下步骤：

1. 开始于根节点：查询开始于包含键2的根节点。
2. 沿右子节点前进：因为6大于2，我们沿着指向键大于2的子节点的指针前进。
3. 在中间层继续比较：在接下来的节点中，我们比较键值，确定应该沿哪个子节点前进，直到到达包含键6的叶子节点。
4. 访问数据行：在叶子节点中，键6对应的指针将指向实际存储图书ID为6的图书信息的数据行。

通过这种方式，B+树索引大大减少了需要检查的数据行数，从而提高了查询效率，特别是在处理大量数据时。