biscuitの博客

B+树的定义#

B+树是一种平衡树，是B树的变种。

B+树的所有关键字都在叶子节点上，从左到右，从小到大有序排列；叶子之间通过指针连接，形成一个有序链表，方便范围查询。

• 优势：可以用头指针顺序便利，不用像B树那样中序遍历。

B+树的非叶子节点只存储索引信息，不存储实际数据。每个非叶子节点的关键字是其子节点中最大关键字的副本。

单个节点最多m个分支的B+树称为m阶B+树，具有以下性质：

• 平衡：B+树通过调整节点的分裂和合并来保持树的平衡，确保所有叶子节点在同一层，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。

• 有序：B+树的叶子节点中的关键字是有序排列的，且通过指针连接，支持范围查询。

• 多路：对于m阶B+树：

  1. 每个非叶子节点最多有m个子节点，至少有⌈m/2⌉个子节点（根节点除外）。

  2. 每个非叶子节点内可以存储最多m个关键字，至少存储⌈m/2⌉-1个关键字（根节点除外）。叶子节点至少存储⌈(m-1)/2⌉个关键字。

  3. k个分支的非叶子节点有k个关键字。

WARNING

这里和B树的区别是B树的一个关键字可以有左右两个子节点，而B+树的一个关键字对应一个子节点。

B+树是数据库和文件系统中常用的索引结构，适合大规模数据的存储和查询。相当于索引的索引，只有叶子节点才有数据的地址，所以随机访问时要查到叶子节点才能找到数据。