# B+Tree详细讲解

## B+Tree的定义

B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：

* 有m个子树的节点包含有m个元素（B-Tree中是m-1）
* 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
* 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
* 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9gzghP5bac7Q0r1%2F831179-20170727155517883-253845810.png?generation=1573735149088967\&alt=media)

## 更直观的图

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9h1s8bvxObA98tH%2F831179-20170727161516618-309588696.png?generation=1573735149165893\&alt=media)

> * 红点表示是指向卫星数据的指针，指针指向的是存放实际数据的磁盘页，卫星数据就是数据库中一条数据记录。
> * 叶子节点中还有一个指向下一个叶子节点的next指针，所以叶子节点形成了一个有序的链表，方便遍历B+树。

## B+树的优势

### 1.更加高效的单元素查找

B+树的查找元素3的过程：

**第一次磁盘IO**

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9h31RQyIsQxFcmy%2F831179-20170727164727368-1815008301.png?generation=1573735149021686\&alt=media)

**第二次磁盘IO**

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9h5im1laIV8R2Wo%2F831179-20170727164821274-2109260481.png?generation=1573735149186774\&alt=media)

**第三次磁盘IO**

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9h7ByoABzSSOwqC%2F831179-20170727164850993-1053507218.png?generation=1573735149054122\&alt=media)

这个过程看下来，貌似与B树的查询过程没有什么区别。但实际上有两点不一样：

a、首先B+树的中间节点不存储卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素，如此一来，相同数量的数据下，B+树就相对来说要更加矮胖些，磁盘IO的次数更少。

b、由于只有叶子节点才保存卫星数据，B+树每次查询都要到叶子节点；而B树每次查询则不一样，最好的情况是根节点，最坏的情况是叶子节点，没有B+树稳定。

### 2.叶子节点形成有顺链表，范围查找性能更优

**B树范围查找3-8的过程**

a、先查找3

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9h9YAmGy57a-8Ai%2F831179-20170726204440265-1470875410.png?generation=1573735149045505\&alt=media)

b、再查找4、5、6、7、8，中间过程省略，直接到8的查找

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9hBJVHxJEUoAUOQ%2F831179-20170726204557218-278418125.png?generation=1573735148966042\&alt=media)

这里查找的范围跨度越大，则磁盘IO的次数越多，性能越差。

**B+树范围查找3-11的过程**

![](https://530416962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtduzqE1l4TlPC2D3SH%2F-Ltdv-y6sBZiYDUuy_7L%2F-Ltdv9hDIMRFIuc0_oI6%2F831179-20170727170747243-354328993.png?generation=1573735149218324\&alt=media)

先从上到下找到下限元素3，然后通过链表指针，依次遍历得到元素5/6/8/9/11；如此一来，就不用像B树那样一个个元素进行查找。

## 总结

1.单节点可以存储更多的元素，使得查询磁盘IO次数更少。

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

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

PS:在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。