当前位置：首页 > news >正文

第十九：b+树和b-树

news 来源：原创 2025/8/22 9:38:37

优点一： B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。

优点二： B+树所有的Data域在叶子节点，并且所有叶子节点之间都有一个链指针。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

1）B+树空间利用率更高，可减少I/O次数

B+树的叶子节点是按顺序放置的双向链表

3）B+树的查询效率更加稳定

因为B+树的每次查询过程中，都需要遍历从根节点到叶子节点的某条路径。所有关键字的查询路径长度相同，导致每一次查询的效率相当。

只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。

后来又在B+树上增加了顺序访问指针，也就是每个叶子节点增加一个指向相邻叶子节点的指针，这样一棵树成了数据库系统实现索引的首选数据结构。

小结：B树和B+树的区别

1）B树的每个结点都存储了key和data，B+树的data存储在叶子节点上。

节点不存储data，这样一个节点就可以存储更多的key。可以使得树更矮，所以IO操作次数更少。

2）树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录

由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

树高度越小，I/O次数越少。为什么是B+树而不是B树呢，因为它内节点不存储data，这样一个节点就可以存储更多的key。

B 树：在 B 树中，所有的节点（包括叶节点和内部节点）都存储数据。对于一个节点，它的键值和数据一并存储。查找过程中，如果找到了匹配的键，则返回相应的数据。

B+ 树：与 B 树不同，B+ 树的所有数据都存储在叶节点中，非叶节点只存储键值，并且起到索引作用。在 B+ 树中，叶节点之间通过指针连接，形成一个链表，这使得范围查询更加高效。
————————————————

范围查询性能更好：

B+ 树的叶节点按照顺序连接形成链表，这使得范围查询时，可以顺序扫描叶节点，非常高效。而 B 树的节点存储了数据，每次范围查询都需要频繁跳转到不同的节点，性能较差。
数据存储集中在叶节点：B+ 树的数据集中在叶节点，不会占用内部节点的存储空间，这使得 B+ 树的叶节点可以存储更多的数据，减少磁盘 I/O 操作。
一致性更高：由于 B+ 树非叶节点不存储数据，只存储键值，它们的高度更低，减少了搜索的复杂度。
————————————————

B+ 树的优势
优化磁盘存储：B+ 树通过较大的节点大小来提高磁盘存取效率，可以一次性读取更多的键值，从而减少磁盘 I/O 次数。
顺序遍历性能：B+ 树的叶节点之间有链表结构，适合做范围查询，顺序遍历叶节点时性能更高。
支持大数据量：由于 B+ 树的节点可以存储更多的键值，它能够处理更大规模的数据。
良好的缓存命中率：较高的节点容量可以让更多的键值存储在内存中，提升缓存的命中率，减少磁盘访问。
————————————————

B+ 树：数据存储在叶节点，内部节点仅存储键值，叶节点通过链表连接，支持高效的范围查询和较少的磁盘 I/O。

B+树的叶子节点存储数据，而非叶子节点只存储指针，不存储数据。B树的所有节点（包括叶子节点）都存储数据，数据分布在整个树结构中。

叶子节点连接：B+树的叶子节点通过有序的双向链表相连，而B树的叶子节点不相连。
🔍 区间查询效率：由于B+树的叶子节点相连，范围查询效率更高。因此，在存在大量范围查询的场景中，B+树更为适合。而对于大量单个key查询的场景，B树可能更合适

总结：

特性	B树（B-Tree）	B+树（B+Tree）
节点存储内容	内部节点和叶子节点都存储数据	只有叶子节点存储数据，内部节点只存储键
叶子节点结构	叶子节点之间没有直接链接	叶子节点通过双向链表连接，支持快速遍历
插入/删除操作	插入/删除可能影响多个层级的节点	插入/删除主要集中在叶子节点，稳定性好
磁盘I/O优化	每个节点存储数据，磁盘I/O次数较多	内部节点只存储键，磁盘I/O次数较少
适用场景	适合精确查询，范围查询性能较差	适合精确查询和范围查询，性能更好

所有值只存储在叶子节点中。
非叶子节点只存储关键字和指向子节点的指针。
叶子节点之间通过指针相连，形成一个有序链表，这使得范围查询非常高效。
非叶子节点不存储数据，只存储键值和指向子节点的指针，这样可以使得内部节点更加紧凑，减少了磁盘I/O操作的需求。

相关文章：