存储方式不同:B 树的每个节点都存储数据,而 B+树的非叶子节点仅存储索引信息,数据都存储在叶子节点中。
叶子节点结构不同:B 树的叶子节点存储数据和指针,而 B+树的叶子节点仅存储数据,而且数据是按照键值大小有序存储的,相邻的叶子节点之间还有指针相连,形成链表结构。
遍历方式不同:B 树遍历时需要每个节点进行查找,而 B+ 树可以通过叶子节点形成的链表直接遍历所有数据。
应用场景不同:由于B+树的数据都存储在叶子节点中,因此可以使用更大的块大小,从而减少磁盘I/O操作,适合于数据库等需要高效查询和插入的场景;而B树适合于内存中的数据结构,或者对磁盘I/O次数要求不是很高的场景。
B+ 树非叶子节点仅存储 key 不存储 data ,这样一个节点就可以存储更多的 key,可以使得 B+ 树相对 B 树来说更矮(IO次数就是树的高度),所以与磁盘交换的 IO 操作次数更少。
由于数据顺序排列并且相连,所以便于区间查找和搜索。而 B 树则需要进行每一层的递归遍历,相邻的元素可能在内存中不相邻,所以缓存命中性没有 B+ 树好。