B+树

B+树(B+ Tree)是B树的一种变体,是一种多路平衡查找树。它的所有关键字数据都保存在叶子节点中,内部节点仅存储索引用的关键字,叶子节点之间还以链表相连,非常适合作为磁盘上的索引结构。

概述

B+树的每个节点可以拥有多个子节点(即多路),这使得树的高度很低,查找任意记录只需少量磁盘访问。与B树不同,B+树的内部节点不存放实际数据,只存放用于导航的键和指向子节点的指针,而所有真正的数据记录都集中在最底层的叶子节点。叶子节点按键有序排列并通过指针串联成一条链表,使得顺序遍历和范围查询非常高效。

核心特点

• 数据集中在叶子:非叶子节点只做索引,所有记录都在叶子层,查询路径长度一致。
• 多路降低高度:一个节点容纳大量键,使树保持很低的高度,减少磁盘I/O。
• 叶子链表:叶子节点顺序链接,支持高效的范围扫描和排序输出。
• 自平衡:插入和删除通过节点的分裂与合并保持树的平衡。

应用场景

B+树是关系型数据库索引的主流实现,主流数据库的聚簇索引和二级索引大多基于B+树。文件系统也常用B+树组织目录和文件的元数据,以支持快速查找和有序遍历。由于它对磁盘友好且天然支持范围查询,凡是需要在大规模有序数据上做点查询和范围查询的存储系统,都倾向采用B+树。

常见问题

问:B+树和B树的主要区别是什么?答:B树的内部节点也存储数据,而B+树把所有数据都放在叶子节点,内部节点只存索引键;此外B+树的叶子节点用链表相连,更利于范围查询。B+树因此在数据库索引场景中比B树更受欢迎。

问:为什么数据库索引偏爱B+树而不是二叉搜索树?答:二叉搜索树每个节点只有两个分支,存储海量数据时树会很高,每次查找都对应大量磁盘随机访问。B+树是多路结构,单个节点容纳许多键,树高极低,能把磁盘I/O次数降到很少,因而更适合磁盘存储。