> For the complete documentation index, see [llms.txt](https://maxwell.gitbook.io/way-to-architect/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maxwell.gitbook.io/way-to-architect/shu-ju-ku/mysql/mysqlsuo-yin/b-treeb+treegai-shu.md).

# B-Tree/B+Tree概述

## B-Tree的数据结构

为了描述B-Tree，首先定义一条数据记录为一个二元组\[key, data]：

* * key为记录的键值，对于不同数据记录，key是互不相同的；
  * data为数据记录除key外的数据。

那么B-Tree是满足下列条件的数据结构：（其中，h为B-Tree的高度，d为B-Tree的度，且d>1，h>0）

* * 每个非叶子节点由n-1个key和n个指针组成（其中d<=n<=2d），且这些key是有序的；
  * 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null ；
  * 所有叶节点具有相同的深度，等于树高h；
  * key和指针互相间隔，节点两端是指针；
  * 一个节点中的key从左到右非递减排列。
  * 所有节点组成树结构。
  * 每个指针要么为null，要么指向另外一个节点。
  * 如果某个指针在节点node最左边且不为null，则其指向节点的所有`key < key1`，其中key1为node的第一个key的值。
  * 如果某个指针在节点node最右边且不为null，则其指向节点的所有`key ≥ keym`，其中keym为node的最后一个key的值。
  * 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1，则其指向节点的所有key满足：`keyi ≤ key <  keyi+1`。

如下为B-Tree的示意图，高度h=2，节点数为5：![](https://1360295607-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LATEhlAPqBUOhHPcpUO%2F-LN3SUlEVZsKLhgCCoo9%2F-LN3SmGV4K0A0DOiEpiH%2F%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-23%20%E4%B8%8A%E5%8D%8811.22.09.png?generation=1537673209862491\&alt=media)由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：**首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败**。

但是，由于插入/删除数据记录会破坏B-Tree的性质，因此在插入/删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

## B+Tree

B-Tree有许多变种，其中最常见的是B+Tree。与B-Tree相比，B+Tree有以下不同点：

* * 每个节点的指针上限为2d而不是2d+1；
  * 内节点只存储key和指针，不存储data，叶子节点不存储指针，只存储key和data；

> 内节点：或内部节点，是指除去树最下面的叶子节点和根节点的其余节点；
>
> 子节点：对每个B+Tree的节点而言，其实都是由n个子节点组成的，比如2-3B-Tree（2-3树），每个节点只可能有 2 或 3 个子节点；

如下为B+Tree的示意图：

![](https://1360295607-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LATEhlAPqBUOhHPcpUO%2F-LN3SUlEVZsKLhgCCoo9%2F-LN3SmGXMQT52b0Ljhua%2F%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-23%20%E4%B8%8A%E5%8D%8811.22.22.png?generation=1537673210006276\&alt=media)

由于并不是所有节点都具有相同的域（指针/key/data），因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关。

## 带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

![](https://1360295607-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LATEhlAPqBUOhHPcpUO%2F-LN3SUlEVZsKLhgCCoo9%2F-LN3SmGZSM2BVY2TQNWw%2F%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-23%20%E4%B8%8A%E5%8D%8811.22.32.png?generation=1537673209852595\&alt=media)

如上图所示：在B+Tree的基础之上，每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提高了区间查询效率。

## 内容来源

[B-Tree和B+Tree](https://www.kancloud.cn/kancloud/theory-of-mysql-index/41844)，改正了两处不准确的地方，重画了图例。

[维基百科 B+树](https://zh.wikipedia.org/wiki/B%2B树)