1.B-树（就是B树）

下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

• 1.根结点至少有两个子女。

• 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

• 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

• 4.所有的叶子结点都位于同一层。

• 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

1.1查找

• 单值查找：最好就是在根节点，否则就是最下叶子节点。
• 范围查找：查找下限，然后中序遍历。

应用

• MongoDB

2.B+树

一个m阶的B树具有如下几个特征：

• 1.根结点至少有两个子女。

• 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

• 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

• 4.所有的叶子结点都位于同一层。

• 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

2.1优势

B+树的优势：

• 1.单一节点存储更多的元素，使得查询的IO次数更少。

• 2.所有查询都要查找到叶子节点，查询性能稳定。

• 3.所有叶子节点形成有序链表，便于范围查询。

https://mp.weixin.qq.com/s/20rexepuT3YytkZJDOfVqw