目录一、索引的使命从线性搜索到对数定位二、B树的节点结构扇出是关键三、插入与分裂向上生长的动态平衡四、删除与合并萎缩时的结构回收五、叶子节点链表范围查询的秘密武器六、扇出与高度的现实计算七、结语工程选择的收敛一、索引的使命从线性搜索到对数定位在没有索引的堆文件中一条等值查询的执行路径是清晰的——也是低效的。系统从第一个数据页开始逐页读入缓冲池逐行检查是否满足查询条件直到找到目标记录或扫描完整个文件。对于N个数据页的表这种策略的平均查询代价是N/2次磁盘IO——线性复杂度。二分查找可以将查询代价降低到对数级但前提是记录必须按照查找键物理有序存储且系统能够随机访问任意位置的记录。磁盘的物理特性恰恰不利于这种随机访问——每一次跳跃到新的中间位置都可能触发一次新的随机IO。对于存储在磁盘上的数据二分查找的对数复杂度只是理论上的实际的常数因子——每次定位的寻道时间——使得这种策略在纯磁盘环境下表现不佳。索引的本质是在数据文件之外构建一组辅助查找结构。这组结构占用的空间远小于数据文件本身却能够以对数级的IO次数定位到目标数据页。索引不改变数据文件的物理组织而是在其上叠加了一层导航层——就像一本书的目录不改变正文的排列顺序却能让读者快速跳转到目标章节。在数据库系统半个多世纪的发展历程中多种索引结构曾被提出和实践——哈希索引、ISAM索引、AVL树、红黑树、B树、B树。最终B树几乎统一了这个战场。它的胜出不是某个单一指标的优势而是对磁盘物理特性、查询模式多样性和维护代价的系统性回应。二、B树的节点结构扇出是关键B树是一种多路搜索树其设计核心可以用一句话概括让每个节点存储尽可能多的键值从而将整棵树的高度压缩到最低。理解这一设计需要首先审视磁盘IO的特性——在第19篇中我们已指出顺序IO远比随机IO高效而索引查找本质上是沿树从上到下的随机IO路径。减少这组路径的长度是索引结构优化的首要目标。B树的每个节点对应一个磁盘页面。节点内部存储一组有序的键值和子节点指针。对于非叶子节点每个键值为其左侧子树的最大值或右侧子树的最小值指针指向下一层的子节点页面。键值在节点内部有序排列节点之间也维持全局有序——父节点的键值准确地划定了各子节点所覆盖的键值范围。B树的关键参数是扇出——每个节点能够容纳的子节点指针数量。扇出取决于页面大小和键值长度。以典型的配置为例页面大小为16KB每个键值指针对占用约32字节例如8字节的整数键8字节的页面指针开销则单个节点可容纳约500个键值对即扇出约为500。这个看似平淡无奇的数字正是B树强大性能的数学根源。一棵三层的B树根节点→中间节点→叶子节点在扇出为500时可以索引的数据页数量为根节点500个指针 → 500个中间节点每个中间节点500个指针 → 500×500 250,000个叶子节点每个叶子节点对应一个数据页 → 250,000个数据页若每个数据页存储100条记录则三层B树可以索引2500万条记录。而查找任意一条记录所需的IO次数仅为3次——根节点一次通常常驻缓冲池、中间节点一次、叶子节点一次。若根节点在缓冲池中命中实际磁盘IO仅2次。当数据量增长到百亿级别时B树仅需增加至四层——四层可索引的记录数约为500³×100 125亿条记录。高度的增长与数据量的增长呈对数关系且对数的底数是扇出而非2。这是B树区别于二叉搜索树的核心优势——二叉树的对数底数为2索引一百万条记录需要约20层B树以数百为底数索引百万条记录仅需2到3层。三、插入与分裂向上生长的动态平衡B树的高扇出解释了它为何能以极小的高度索引海量数据。但一个索引结构不仅需要高效的查询能力还必须能够在数据动态增长时维持其高效的结构。B树通过插入时自底向上的分裂机制来实现动态平衡。当向B树中插入一条新记录的键值时系统首先从根节点开始向下遍历根据键值比较结果找到应插入的叶子节点。如果该叶子节点有空闲空间当前键值数量小于最大容量键值按序插入操作完成。如果叶子节点已满则发生节点分裂。节点分裂的算法步骤清晰而严谨系统首先申请一个新的数据页作为分裂节点。将原节点的键值加上待插入的新键值共计M1个键值排序后一分为二——前一半保留在原节点后一半迁移至新节点。分裂点的键值通常取前半部分的最后一个键值连同新节点的指针被插入到父节点中作为父节点中指向新节点的导航键。父节点接收到新的键值-指针对后可能也面临空间不足而需要分裂。这种分裂行为沿着树自底向上传播——最坏情况下分裂可能一直传导到根节点。当根节点也需要分裂时B树向上生长一层一个新的根节点被创建其两个子指针分别指向原根节点和分裂产生的新节点。这是B树高度增加的唯一情形——由根分裂触发整棵树的高度同步加一。这个向上生长的机制保证了B树始终是高度平衡的——从根节点到任意叶子节点的路径长度完全相同。无论插入了多少记录无论插入的顺序如何B树永远不会出现某些分支极深、某些分支极浅的不平衡状态。每一次查询的IO次数都是确定而稳定的不存在二叉树在顺序插入时退化为链表的性能陷阱。以一个具体数值演示分裂过程。假设一个B树的节点最大容量为4个键值简化起见实际扇出远大于此。叶子节点L₁已有键值[10, 20, 30, 40]。插入键值25时节点满触发分裂。排序后序列为[10, 20, 25, 30, 40]前一半[10, 20]保留在L₁后一半[30, 40]迁移至新节点L₂分裂键25连同L₂的指针插入父节点。若父节点原有键值[15, 50]插入25后序列为[15, 25, 50]未超出容量分裂停止。四、删除与合并萎缩时的结构回收数据不仅会增长也会被删除。当键值从B树中被删除时可能触发与分裂对称的反向操作——节点合并。删除操作首先定位到包含目标键值的叶子节点移除该键值。如果删除后节点的键值数量仍不低于最低填充阈值通常为最大容量的一半即⌈M/2⌉操作完成。如果键值数量跌破阈值系统面临两种选择。第一种选择是借键——如果相邻的兄弟节点键值数量充裕超过最低阈值可以从兄弟节点“借用”一个键值来充实自身。借键操作涉及将兄弟节点的一个边界键值迁移到当前节点并更新父节点中对应的分隔键值。借键避免了节点数量的变化仅需在局部调整键值分布。第二种选择是合并——如果相邻兄弟节点也不充裕则当前节点与兄弟节点合并为一个节点。合并后父节点中指向这两个子节点的两个指针需要合并为一个指针这导致父节点中一个键值被删除。父节点的键值删除又可能引发父节点的下溢导致合并操作沿树向上传播。最极端的情况下合并传播到根节点且根节点只剩下一个子指针时根节点被移除整个树的高度减一。合并与分裂共同构成了B树的自我调节机制——树随数据增长而增高随数据萎缩而降低始终保持高度与数据量的对数关系。这两套机制使得B树在动态数据集上维持了结构平衡无需数据库管理员的手动干预。五、叶子节点链表范围查询的秘密武器B树区别于它的前身B树的一个关键特征在于所有叶子节点通过链表串联在一起。在叶子节点内部键值有序排列在叶子节点之间每个叶子节点包含指向下一个兄弟叶子节点的指针。这个链表结构的威力在范围查询中展露无遗。当系统需要执行WHERE 键值 BETWEEN A AND B时它首先沿B树从根到叶子查找键值A所在的叶子节点对数级IO然后沿着叶子节点链表顺序扫描——从A开始依次访问链表中的每个叶子节点读取其中的记录直到键值超过B为止。这个过程充分利用了顺序IO和随机IO的优势分工树的纵向遍历根到叶子是少数几次随机IO精确定位范围起点叶子节点链表的横向扫描是顺序IO以磁盘的最大吞吐量读取连续的数据。这种“纵向索引横向扫描”的模式完美契合了磁盘物理特性——随机寻道找到起点顺序读取覆盖全程。相比之下B树不具备叶子节点链表范围查询需要不断回到上层节点寻找后继随机IO次数远高于B树。哈希索引则彻底无法支持范围查询——哈希函数将键值映射为无关联的桶号相邻键值的记录四散在毫无关联的存储位置中。这一结构差异正是B树在关系数据库领域全面压过B树和哈希索引的根本原因——关系模型中的典型查询不仅包括等值查询还包括范围查询、前缀查询、排序输出而B树对所有这些查询模式都提供了结构性的支持。六、扇出与高度的现实计算行文至此我们可以进行一次现实场景的计算以更具体地感知B树的物理性能。假设数据库使用InnoDB存储引擎页面大小为16KB16384字节。表的主码为8字节的BIGINT。B树非叶子节点的每个条目包括8字节的键值8字节的子节点页面指针约4字节的元数据开销约20字节。一个页面可容纳约16384/20≈819个条目扇出约为819。叶子节点每个条目包括记录数据假设平均记录长度为200字节每个叶子节点可容纳约80条记录。三层B树——根节点层1→ 中间节点层2→ 叶子节点层3——可索引的记录数819根扇出×819中间节点扇出×80每叶记录数≈5300万条记录。查找任意一条记录的IO次数根节点通常命中缓冲池中间节点叶子节点2至3次磁盘IO。当表增长至10亿条记录时仅需增加至四层。四层可容纳819³×80≈435亿条记录10亿条记录的表高仍在四层以内。每次查询的IO次数不超过4次且根节点和部分中间节点在运行中会被缓冲池长期驻留实际IO常常仅为1至2次。这组数字有力地说明了为什么B树能够成为索引结构的统治性选择——在数据量增长数万倍的过程中查询IO次数仅从2次增加到4次对数复杂度的常数因子极其稳健。这种近乎平坦的性能曲线正是数据库系统能够支撑互联网级数据规模而不发生查询性能崩塌的底层保障。七、结语工程选择的收敛B树不是索引结构竞赛中的偶然胜出者。它的每一个设计特征都精准地回应了存储硬件的一类物理约束高扇出对抗磁盘寻道的延迟高度平衡对抗数据分布的不确定性叶子节点链表对抗范围查询的随机跳跃分裂与合并对抗数据量的动态变化。其他索引结构——哈希索引、二叉树、ISAM——各自在一两项指标上可能优于B树但在面对关系数据库混合负载等值查询、范围查询、排序输出、动态更新的综合考验时B树提供了最均衡、最稳健的整体表现。下一篇我们将从B树的骨架转向索引家族的其他成员——哈希索引、位图索引与全文索引。它们在特定场景下各自拥有B树难以企及的优势理解它们的原理与适用边界才能在不同的业务需求下做出精准的索引选择。
【数据库系统原理】第21篇：索引的骨架：B+树数据结构的深度解析
发布时间：2026/6/25 22:19:35
目录一、索引的使命从线性搜索到对数定位二、B树的节点结构扇出是关键三、插入与分裂向上生长的动态平衡四、删除与合并萎缩时的结构回收五、叶子节点链表范围查询的秘密武器六、扇出与高度的现实计算七、结语工程选择的收敛一、索引的使命从线性搜索到对数定位在没有索引的堆文件中一条等值查询的执行路径是清晰的——也是低效的。系统从第一个数据页开始逐页读入缓冲池逐行检查是否满足查询条件直到找到目标记录或扫描完整个文件。对于N个数据页的表这种策略的平均查询代价是N/2次磁盘IO——线性复杂度。二分查找可以将查询代价降低到对数级但前提是记录必须按照查找键物理有序存储且系统能够随机访问任意位置的记录。磁盘的物理特性恰恰不利于这种随机访问——每一次跳跃到新的中间位置都可能触发一次新的随机IO。对于存储在磁盘上的数据二分查找的对数复杂度只是理论上的实际的常数因子——每次定位的寻道时间——使得这种策略在纯磁盘环境下表现不佳。索引的本质是在数据文件之外构建一组辅助查找结构。这组结构占用的空间远小于数据文件本身却能够以对数级的IO次数定位到目标数据页。索引不改变数据文件的物理组织而是在其上叠加了一层导航层——就像一本书的目录不改变正文的排列顺序却能让读者快速跳转到目标章节。在数据库系统半个多世纪的发展历程中多种索引结构曾被提出和实践——哈希索引、ISAM索引、AVL树、红黑树、B树、B树。最终B树几乎统一了这个战场。它的胜出不是某个单一指标的优势而是对磁盘物理特性、查询模式多样性和维护代价的系统性回应。二、B树的节点结构扇出是关键B树是一种多路搜索树其设计核心可以用一句话概括让每个节点存储尽可能多的键值从而将整棵树的高度压缩到最低。理解这一设计需要首先审视磁盘IO的特性——在第19篇中我们已指出顺序IO远比随机IO高效而索引查找本质上是沿树从上到下的随机IO路径。减少这组路径的长度是索引结构优化的首要目标。B树的每个节点对应一个磁盘页面。节点内部存储一组有序的键值和子节点指针。对于非叶子节点每个键值为其左侧子树的最大值或右侧子树的最小值指针指向下一层的子节点页面。键值在节点内部有序排列节点之间也维持全局有序——父节点的键值准确地划定了各子节点所覆盖的键值范围。B树的关键参数是扇出——每个节点能够容纳的子节点指针数量。扇出取决于页面大小和键值长度。以典型的配置为例页面大小为16KB每个键值指针对占用约32字节例如8字节的整数键8字节的页面指针开销则单个节点可容纳约500个键值对即扇出约为500。这个看似平淡无奇的数字正是B树强大性能的数学根源。一棵三层的B树根节点→中间节点→叶子节点在扇出为500时可以索引的数据页数量为根节点500个指针 → 500个中间节点每个中间节点500个指针 → 500×500 250,000个叶子节点每个叶子节点对应一个数据页 → 250,000个数据页若每个数据页存储100条记录则三层B树可以索引2500万条记录。而查找任意一条记录所需的IO次数仅为3次——根节点一次通常常驻缓冲池、中间节点一次、叶子节点一次。若根节点在缓冲池中命中实际磁盘IO仅2次。当数据量增长到百亿级别时B树仅需增加至四层——四层可索引的记录数约为500³×100 125亿条记录。高度的增长与数据量的增长呈对数关系且对数的底数是扇出而非2。这是B树区别于二叉搜索树的核心优势——二叉树的对数底数为2索引一百万条记录需要约20层B树以数百为底数索引百万条记录仅需2到3层。三、插入与分裂向上生长的动态平衡B树的高扇出解释了它为何能以极小的高度索引海量数据。但一个索引结构不仅需要高效的查询能力还必须能够在数据动态增长时维持其高效的结构。B树通过插入时自底向上的分裂机制来实现动态平衡。当向B树中插入一条新记录的键值时系统首先从根节点开始向下遍历根据键值比较结果找到应插入的叶子节点。如果该叶子节点有空闲空间当前键值数量小于最大容量键值按序插入操作完成。如果叶子节点已满则发生节点分裂。节点分裂的算法步骤清晰而严谨系统首先申请一个新的数据页作为分裂节点。将原节点的键值加上待插入的新键值共计M1个键值排序后一分为二——前一半保留在原节点后一半迁移至新节点。分裂点的键值通常取前半部分的最后一个键值连同新节点的指针被插入到父节点中作为父节点中指向新节点的导航键。父节点接收到新的键值-指针对后可能也面临空间不足而需要分裂。这种分裂行为沿着树自底向上传播——最坏情况下分裂可能一直传导到根节点。当根节点也需要分裂时B树向上生长一层一个新的根节点被创建其两个子指针分别指向原根节点和分裂产生的新节点。这是B树高度增加的唯一情形——由根分裂触发整棵树的高度同步加一。这个向上生长的机制保证了B树始终是高度平衡的——从根节点到任意叶子节点的路径长度完全相同。无论插入了多少记录无论插入的顺序如何B树永远不会出现某些分支极深、某些分支极浅的不平衡状态。每一次查询的IO次数都是确定而稳定的不存在二叉树在顺序插入时退化为链表的性能陷阱。以一个具体数值演示分裂过程。假设一个B树的节点最大容量为4个键值简化起见实际扇出远大于此。叶子节点L₁已有键值[10, 20, 30, 40]。插入键值25时节点满触发分裂。排序后序列为[10, 20, 25, 30, 40]前一半[10, 20]保留在L₁后一半[30, 40]迁移至新节点L₂分裂键25连同L₂的指针插入父节点。若父节点原有键值[15, 50]插入25后序列为[15, 25, 50]未超出容量分裂停止。四、删除与合并萎缩时的结构回收数据不仅会增长也会被删除。当键值从B树中被删除时可能触发与分裂对称的反向操作——节点合并。删除操作首先定位到包含目标键值的叶子节点移除该键值。如果删除后节点的键值数量仍不低于最低填充阈值通常为最大容量的一半即⌈M/2⌉操作完成。如果键值数量跌破阈值系统面临两种选择。第一种选择是借键——如果相邻的兄弟节点键值数量充裕超过最低阈值可以从兄弟节点“借用”一个键值来充实自身。借键操作涉及将兄弟节点的一个边界键值迁移到当前节点并更新父节点中对应的分隔键值。借键避免了节点数量的变化仅需在局部调整键值分布。第二种选择是合并——如果相邻兄弟节点也不充裕则当前节点与兄弟节点合并为一个节点。合并后父节点中指向这两个子节点的两个指针需要合并为一个指针这导致父节点中一个键值被删除。父节点的键值删除又可能引发父节点的下溢导致合并操作沿树向上传播。最极端的情况下合并传播到根节点且根节点只剩下一个子指针时根节点被移除整个树的高度减一。合并与分裂共同构成了B树的自我调节机制——树随数据增长而增高随数据萎缩而降低始终保持高度与数据量的对数关系。这两套机制使得B树在动态数据集上维持了结构平衡无需数据库管理员的手动干预。五、叶子节点链表范围查询的秘密武器B树区别于它的前身B树的一个关键特征在于所有叶子节点通过链表串联在一起。在叶子节点内部键值有序排列在叶子节点之间每个叶子节点包含指向下一个兄弟叶子节点的指针。这个链表结构的威力在范围查询中展露无遗。当系统需要执行WHERE 键值 BETWEEN A AND B时它首先沿B树从根到叶子查找键值A所在的叶子节点对数级IO然后沿着叶子节点链表顺序扫描——从A开始依次访问链表中的每个叶子节点读取其中的记录直到键值超过B为止。这个过程充分利用了顺序IO和随机IO的优势分工树的纵向遍历根到叶子是少数几次随机IO精确定位范围起点叶子节点链表的横向扫描是顺序IO以磁盘的最大吞吐量读取连续的数据。这种“纵向索引横向扫描”的模式完美契合了磁盘物理特性——随机寻道找到起点顺序读取覆盖全程。相比之下B树不具备叶子节点链表范围查询需要不断回到上层节点寻找后继随机IO次数远高于B树。哈希索引则彻底无法支持范围查询——哈希函数将键值映射为无关联的桶号相邻键值的记录四散在毫无关联的存储位置中。这一结构差异正是B树在关系数据库领域全面压过B树和哈希索引的根本原因——关系模型中的典型查询不仅包括等值查询还包括范围查询、前缀查询、排序输出而B树对所有这些查询模式都提供了结构性的支持。六、扇出与高度的现实计算行文至此我们可以进行一次现实场景的计算以更具体地感知B树的物理性能。假设数据库使用InnoDB存储引擎页面大小为16KB16384字节。表的主码为8字节的BIGINT。B树非叶子节点的每个条目包括8字节的键值8字节的子节点页面指针约4字节的元数据开销约20字节。一个页面可容纳约16384/20≈819个条目扇出约为819。叶子节点每个条目包括记录数据假设平均记录长度为200字节每个叶子节点可容纳约80条记录。三层B树——根节点层1→ 中间节点层2→ 叶子节点层3——可索引的记录数819根扇出×819中间节点扇出×80每叶记录数≈5300万条记录。查找任意一条记录的IO次数根节点通常命中缓冲池中间节点叶子节点2至3次磁盘IO。当表增长至10亿条记录时仅需增加至四层。四层可容纳819³×80≈435亿条记录10亿条记录的表高仍在四层以内。每次查询的IO次数不超过4次且根节点和部分中间节点在运行中会被缓冲池长期驻留实际IO常常仅为1至2次。这组数字有力地说明了为什么B树能够成为索引结构的统治性选择——在数据量增长数万倍的过程中查询IO次数仅从2次增加到4次对数复杂度的常数因子极其稳健。这种近乎平坦的性能曲线正是数据库系统能够支撑互联网级数据规模而不发生查询性能崩塌的底层保障。七、结语工程选择的收敛B树不是索引结构竞赛中的偶然胜出者。它的每一个设计特征都精准地回应了存储硬件的一类物理约束高扇出对抗磁盘寻道的延迟高度平衡对抗数据分布的不确定性叶子节点链表对抗范围查询的随机跳跃分裂与合并对抗数据量的动态变化。其他索引结构——哈希索引、二叉树、ISAM——各自在一两项指标上可能优于B树但在面对关系数据库混合负载等值查询、范围查询、排序输出、动态更新的综合考验时B树提供了最均衡、最稳健的整体表现。下一篇我们将从B树的骨架转向索引家族的其他成员——哈希索引、位图索引与全文索引。它们在特定场景下各自拥有B树难以企及的优势理解它们的原理与适用边界才能在不同的业务需求下做出精准的索引选择。
