Mongo 为什么 MongoDB 使用 B-Tree，MySQL 使用 B+ Tree ?

B+ tree

B+ tree 实际上是一颗m叉平衡查找树(不是二叉树)

平衡查找树定义：树中任意一个节点的左右子树的高度相差不能大于 1

/** 
* 这是B+树非叶子节点的定义。 
* 
* 假设keywords=[3, 5, 8, 10] 
* 4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF) 
* 5个区间分别对应：children[0]...children[4] 
* 
* m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小： 
* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小] 
*/ 
public class BPlusTreeNode { 
  // 5叉树 
  public static int m = 5; 
 
  // 键值，用来划分数据区间 
  public int[] keywords = new int[m-1]; 
 
  // 保存子节点指针 
  public BPlusTreeNode[] children = new BPlusTreeNode[m]; 
} 
/** 
* 这是B+树中叶子节点的定义。 
* 
* B+树中的叶子节点跟内部结点是不一样的, 
* 叶子节点存储的是值，而非区间。 
* 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。 
* 
* k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小： 
* PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小] 
*/ 
public class BPlusTreeLeafNode { 
  public static int k = 3; 
 
  // 数据的键值 
  public int[] keywords = new int[k]; 
 
  // 数据地址 
  public long[] dataAddress = new long[k]; 
 
  // 这个结点在链表中的前驱结点 
  public BPlusTreeLeafNode prev; 
 
  // 这个结点在链表中的后继结点  
  public BPlusTreeLeafNode next; 
} 

在B+ 树中，树中的节点并不存储数据本身，而是只是作为索引。

除此之外，所有记录的节点按大小顺序存储在同一层的叶节点中，并且每个叶节点通过指针连接。

总结下,B+树有以下特点

B +树的每个节点可以包含更多节点，其原因有两个，其一是降低树的高度(索引不会全部存储在内存中,内存中可能撑不住,所以一般都是将索引树存储在磁盘中，只是将根节点放到内存中，这样对每个节点的访问,实际上就是访问磁盘,树的高度就等于每次查询数据时磁盘 IO 操作的次数),另一种是将数据范围更改为多个间隔。

间隔越大，数据检索越快(可以想象跳表)

每个节点不在是存储一个key,而是存储多个key

叶节点来存储数据，而其他节点用于索引

叶子节点通过两个指针相互链接，顺序查询性能更高。

优点

这样设计还有以下优点：

B+ 树的非叶子节点仅存储键，占用很小的空间，因此节点的每一层可以索引的数据范围要宽得多。换句话说，可以为每个IO操作搜索更多数据

叶子节点成对连接，符合磁盘的预读特性。

例如，叶节点存储50和55，它们具有指向叶节点60和62的指针。当我们从磁盘读取对应于50和55的数据时，由于磁盘的预读特性，我们将顺便提一下60和62。读出相应的数据。这次是顺序读取，而不是磁盘搜索，加快了速度。

支持范围查询，局部范围查询非常高效，每个节点都可以索引更大，更准确的范围，这意味着B +树单磁盘IO信息大于B树，并且I / O效率更高

由于数据存储在叶节点层中，并且有指向其他叶节点的指针，因此范围查询仅需要遍历叶节点层，而无需遍历整个树。

由于磁盘访问速度和内存之间存在差距，为了提高效率，应将磁盘I / O最小化。磁盘通常不是严格按需读取的，而是每次都被预读。磁盘读取所需的数据后，它将向后读取内存中的一定长度的数据。这样做的理论基础是计算机科学中众所周知的本地原理：

B-Tree

B-Tree 实际上也是一颗m叉平衡查找树

• 所有的key值分布在整个树中

• 所有的key值出现在一个节点中

• 搜索可以在非叶子节点处结束

• 在完整的关键字搜索过程中，性能接近二分搜索。

B树和B+树之间的区别

B+ 树中的非叶子节点不存储数据，并且存储在叶节点中的所有数据使得查询时间复杂度固定为log n。

B树查询时间的复杂度不是固定的，它与键在树中的位置有关，最好是O(1)。

由于B+树的叶子节点是通过双向链表链接的，所以支持范围查询，且效率比B树高

B树每个节点的键和数据是一起的

Hash 索引

简而言之，哈希索引使用某种哈希算法将键值转换为新的哈希值。

不需要像B +树那样从根节点到叶节点逐步搜索。只需要一种哈希算法,就可以立即找到对应的位置，速度非常快。(此处可以想想Java中的HashMap)。

B+树索引和Hash索引的区别

1.如果是等价查询，则哈希索引显然具有绝对优势，因为只需一种算法即可找到相应的键值;当然，前提是键值是唯一的,如果存在hash冲突就必须链表遍历了。

哈希索引不支持范围查询(不过改造之后可以,Java中的LinkedHashMap通过链表保存了节点的插入顺序,那么也可以使用链表将数据的大小顺序保存起来) 2.这样做虽然支持了范围查询但是时间复杂度是O(n),效率比跳表和B+Tree差

3.哈希索引无法使用索引排序以及模糊匹配

4..哈希索引也不支持多列联合索引的最左边匹配规则。

5.键值大量冲突的情况下,Hash索引效率极低

为什么MongoDB使用B-Tree,Mysql使用B+Tree ?

B+ 树中的非叶子节点不存储数据，并且存储在叶节点中的所有数据使得查询时间复杂度固定为log n。

B树查询时间复杂度不是固定的，它与键在树中的位置有关，最好是O(1)。

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

至于为什么MongoDB使用B树而不是B +树，可以从其设计的角度考虑它。

MongoDB不是传统的关系数据库，而是以BSON格式(可以认为是JSON)存储的nosql。目的是高性能，高可用性和易于扩展。

Mysql是关系型数据库，最常用的是数据遍历操作(join)，而MongoDB它的数据更多的是聚合过的数据，不像Mysql那样表之间的关系那么强烈,因此MongoDB更多的是单个查询。

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

为什么 mongodb 不适用 hash 索引？

既然 MongoDB 认为查询单个数据记录远比遍历数据的查询更加常见，那为什么不使用哈希作为底层的数据结构呢？

如果我们使用哈希，那么对于所有单条记录查询的复杂度都会是 O(1)，但是遍历数据的复杂度就是 O(n)；

如果使用 B+ 树，那么单条记录查询的复杂度是 O(log n)，遍历数据的复杂度就是 O(log n) + X，这两种不同的数据结构一种提供了最好的单记录查询性能，

一种提供了最好的遍历数据的性能，但是这都不能满足 MongoDB 面对的场景 —— 单记录查询非常常见，但是对于遍历数据也需要有相对较好的性能支持。

哈希这种性能表现较为极端的数据结构往往只能在简单、极端的场景下使用。

读多写少

LSM 树是一个基于磁盘的数据结构，它设计的主要目的是为长期需要高频率写入操作的文件提供低成本的索引机制。

无论是 B 树还是 B+ 树，向这些数据结构组成的索引文件中写入记录都需要执行的磁盘随机写，LSM 树的优化逻辑就是牺牲部分的读性能，将随机写转换成顺序写以优化数据的写入。

我们在这篇文章不会详细介绍为什么 LSM 树有着较好的写入性能，我们只是来分析为什么 WiredTiger 使用 B 树作为默认的数据结构。

WiredTiger 对 LSM 树和 B 树的性能进行了读写吞吐量的基准测试，通过基准测试得到了如下图所示的结果，从图中的结果我们能发现：

在不限制写入的情况下；

LSM 树的写入性能是 B 树的 1.5 ~ 2 倍；

LSM 树的读取性能是 B 树的 1/6 ~ 1/3；

在限制写入的情况下；

LSM 树的写入性能与 B 树的性能基本持平；

LSM 树的读取性能是 B 树的 1/4 ~ 1/2；

在限制写入的情况下，每秒会写入 30,000 条数据，从这里的分析结果来看，无论那种情况下 B 树的读取性能是远好于 LSM 树的。

对于大多数的系统来说，系统的查询会是写的很多倍，所以 LSM 树在写入方面的优异表现也没有办法让它成为 MongoDB 默认的数据格式。

总结

应用场景永远都是系统设计时首先需要考虑的问题，作为 NoSQL 的 MongoDB，其目标场景就与更早的数据库就有着比较大的差异，我们来简单总结一下 MongoDB 最终选择使用 B 树的两个原因：

（1）MySQL 使用 B+ 树是因为数据的遍历在关系型数据库中非常常见，它经常需要处理各个表之间的关系并通过范围查询一些数据；但是 MongoDB 作为面向文档的数据库，与数据之间的关系相比，它更看重以文档为中心的组织方式，所以选择了查询单个文档性能较好的 B 树，这个选择对遍历数据的查询也可以保证可以接受的时延；

（2）LSM 树是一种专门用来优化写入的数据结构，它将随机写变成了顺序写显著地提高了写入性能，但是却牺牲了读的效率，这与大多数场景需要的特点是不匹配的，所以 MongoDB 最终还是选择读取性能更好的 B 树作为默认的数据结构；

到最后，我们还是来看一些比较开放的相关问题，有兴趣的读者可以仔细思考一下下面的问题：

BigTable、LevelDB 和 HBase 的应用场景都是什么？

它们的读写比例有多少？

为什么使用 LSM 树作为底层的数据结构？

参考资料

https://www.51cto.com/article/615377.html

https://blog.csdn.net/weixin_41987908/article/details/105255119

https://wenku.baidu.com/view/5d0982ed8aeb172ded630b1c59eef8c75fbf951f.html

https://www.yisu.com/zixun/494591.html

https://baijiahao.baidu.com/s?id=1687107562670296721&wfr=spider&for=pc

https://www.infoq.cn/article/rVYVW4LYPzqX2tqmGk0y

https://www.likecs.com/show-307213317.html

https://www.codenong.com/js9cf1e20b7397/

https://www.freesion.com/article/6983927681/

https://www.bbsmax.com/A/lk5aPjl2J1/

• B+ tree
  • 总结下,B+树有以下特点
  • 优点
• B-Tree
  • B树和B+树之间的区别
• Hash 索引
  • B+树索引和Hash索引的区别
• 为什么MongoDB使用B-Tree,Mysql使用B+Tree ?
  • 为什么 mongodb 不适用 hash 索引？
• 读多写少
• 总结
• 参考资料