MongoDB使用B-Tree，Mysql使用B+Tree？

除了B+-tree，你可能还听说过B-tree和B-tree。其实B树就是B树，英文翻译就是B-Tree。这里的“-”与B+树中的“+”无关，只是一个链接。 B树实际上是B+树的低级版本，或者说B+树是B树的改进版本。

B+-tree

B+-tree实际上是一棵m平衡搜索树（不是二叉树）

平衡搜索树的定义：树中任意节点左右子树的高度差不能大于1

1. 所有键值分布在整棵树上
2. 所有键值出现在一个节点中
3. 搜索即可结束在非叶子节点
4. 在整个关键词搜索过程中，性能接近二分搜索。

B-tree 和 B+-tree 的区别

1. B+-tree 中没有叶子的节点不存储数据，所有数据都存储在叶子节点中，使得查询时间复杂度固定为 log n。
2. 复杂度B树的查询时间不固定，与key在树中的位置有关，最好是O(1)。
3. 由于B+树的叶子节点是通过双向链表连接的，因此支持范围查询，比B树更高效
4. B树中每个节点的key和数据都在一起

为什么MongoDB使用B-Tree，Mysql使用B+Tree？

B+树中不是叶子的节点不存储数据，所有数据存储在叶子节点导致查询时间复杂度固定为log n B树的查询时间复杂度不是固定的，与key在树中的位置有关，最好是O(1)。

我们已经说过，尽可能少地执行磁盘 IO 是提高性能的有效方法。 MongoDB是一个集群数据库，而B树恰好是关键字段和数据字段的集群。

MongoDB为什么使用B-tree而不是B+-tree，可以从设计的角度来考虑。 MongoDB不是传统的关系型数据库，而是以BSON格式（可以认为是JSON）存储的nosql。目标是高性能、高可用性和易于扩展。

Mysql 是一个关系型数据库。用得最多的是数据审核（join），而MongoDB的数据更多的是聚合数据。与Mysql不同，表之间的关系没有那么强，所以MongoDB更多的是单个查询。

因为Mysql采用B+树，数据在叶子节点上，叶子节点通过双向链表连接，更有利于数据遍历，而MongoDB采用B+树，所有节点都有一个数据字段。只要找到指定的索引就可以访问。毫无疑问，单次查询平均MongoDB查询速度比Mysql要快。

哈希索引

简而言之，哈希索引使用某种哈希算法将键值转换为新的哈希值。不需要像B+树那样从根节点到叶节点一步步查找。只需要一种哈希算法就可以立即找到对应的位置，速度非常快。 （这里想想Java中的HashMap）。

B+树索引和哈希索引的区别

1. 如果有对应的查询，哈希索引显然有绝对的优势，因为只有一种算法才能找到对应的键值；当然，假设关键值为唯一的是，如果出现哈希冲突，就必须遍历链表。
2. 哈希索引不支持范围查询（但改造后可以。Java中的LinkedHashMap通过链表存储节点的插入顺序，所以也可以使用链表来存储数据的大小顺序）

这种方式虽然支持Range查询，但时间复杂度为O(n)，效率比跳表和B+3差

1. 哈希索引不能使用索引排序和模糊匹配
2. 哈希索引也不支持匹配规则的最左边公共索引。
3. 大量键值冲突时，哈希索引效率极低

作者：think123
链接：https://juejin.im/post/5ea273f951882573cd41c7a4❀来源版权归归所有由作者。商业转载请联系作者获取授权。非商业转载请注明来源。