数据库为什么使用B+树而不是B树

亦凉 2022-05-14 01:08 218阅读 0赞

###                                               数据库为什么使用B+树而不是B树 ###

### B树和B+树的区别 ###

B树和B+树的区别主要有两点：

1.  在B树中，你可以将键和值存放在内部节点和叶子节点，但在B+树中，内部节点都是键，没有值。叶子节点同时存放键和值
2.  B+树的叶子节点有一条链相连，而B+树的叶子节点各自独立。

### B树与B+树的对比示意图 ###

![treeB-Tree_20And_20B_Tree.png][]

### 使用B+树的好处 ###

1.  由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
2.  B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间

### 使用B树的好处 ###

B树可以在内部节点同时存储键和值，因此，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。这种特性使得B树在特定数据重复多次查询的场景中更加高效。

### 数据库为什么使用B+树而不是B树 ###

因为就是上面提到的B+树的好处。数据库的数据读取都是需要进行代价巨大的磁盘IO操作，因此，更快地缩小范围和更少的读取次数是数据库需要关注的重点。而B+树在这些点上比B树做的更好。这就是为什么数据库要选用B+树作为底层实现。

参考文章：[https://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees\#][https_stackoverflow.com_questions_870218_differences-between-b-trees-and-b-trees]

[treeB-Tree_20And_20B_Tree.png]: http://odwpzo1jp.bkt.clouddn.com/algorithm/treeB-Tree%20And%20B+Tree.png
[https_stackoverflow.com_questions_870218_differences-between-b-trees-and-b-trees]: https://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees#