# B+Tree详细讲解

## B+Tree的定义

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

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

![](/files/-Ltdv9gzghP5bac7Q0r1)

## 更直观的图

![](/files/-Ltdv9h1s8bvxObA98tH)

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

## B+树的优势

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

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

**第一次磁盘IO**

![](/files/-Ltdv9h31RQyIsQxFcmy)

**第二次磁盘IO**

![](/files/-Ltdv9h5im1laIV8R2Wo)

**第三次磁盘IO**

![](/files/-Ltdv9h7ByoABzSSOwqC)

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

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

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

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

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

a、先查找3

![](/files/-Ltdv9h9YAmGy57a-8Ai)

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

![](/files/-Ltdv9hBJVHxJEUoAUOQ)

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

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

![](/files/-Ltdv9hDIMRFIuc0_oI6)

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

## 总结

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

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

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tuonioooo-notebook.gitbook.io/performance-optimization/sqlyou-hua-pian/mysqlyou-hua-pian/b+treejiang-jie/b+treexiang-xi-jiang-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.