# B+ 树 (1): 定义与基本操作

1972 年 R. Bayer 和 E. McCreight 提出了 B- 树（参考 这里）。1979 年 Douglas Comer 在 The Ubiquitous B-Tree 提出了 B- 树的一个变形——B+ 树。由于多路平衡树减少了磁盘读写次数，并且仍然保持 O(logN) 的插入/删除/查找的效率，被广泛应用于数据库和文件系统中。

## 定义（参考资料 [1, 3]）

• 每个节点最多可以有 m 个元素；
• 除了根节点外，每个节点最少有 (m/2) 个元素；
• 如果根节点不是叶节点，那么它最少有 2 个孩子节点；
• 所有的叶子节点都在同一层；
• 一个有 k 个孩子节点的非叶子节点有 (k-1) 个元素，按升序排列；
• 某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它；
• 非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶子节点中；
• 相邻的叶子节点之间用指针相连。

                                             +----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| k | l |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


## 插入

+---+---+---+ insert "p" +---+---+---+ insert "e" +---+---+---+ insert "h" +---+---+---+
|   |   |   |     =>     | p |   |   |     =>     | e | p |   |     =>     | e | h | p |
+---+---+---+            +---+---+---+            +---+---+---+            +---+---+---+


          +------+---+---+                +------+---+---+                +------+---+---+
|      |   |   |                |      |   |   |                |   m  |   |   |
+------+---+---+                +------+---+---+                +------+---+---+
/        \          =>          /        \          =>          /        \
+---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+
| e | h |   |->| p |   |   |    | e | h |   |->| m | p |   |    | e | h |   |->| m | p |   |
+---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+


          +------+---+---+                    +--------+----+---+
|   m  |   |   |                    |    m   |  t |   |
+------+---+---+                    +--------+----+---+
/        \          =>              /         |     \              =>
+---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+  +---+---+---+
| e | h |   |->| m | p | t |    | e | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+    +---+---+---+  +---+---+---+  +---+---+---+

+--------+----+---+
|    m   |  t |   |
+--------+----+---+
/         |     \
+---+---+---+  +---+---+---+  +---+---+---+
| b | e | h |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+


              +---------------+------------+---+
|        m      |     t      |   |
+---------------+------------+---+
/                |             \               =>
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+--------+----------+--------+
|    e   |     m    |    t   |
+--------+----------+--------+
/         |          |         \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


              +--------+----------+--------+
|    e   |     m    |    t   |
+--------+----------+--------+
/         |          |         \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f | h |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


              +--------+-------------------------+--------+
|    e   |            m            |    t   |
+--------+-------------------------+--------+
/         |                         |         \               =>
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+------------------+---+---+
|         m        |   |   |
+------------------+---+---+
/                    \
+----+--------+---+                      +------+---+---+
|  e |        |   |                      |  t   |   |   |    =>
+----+--------+---+                      +------+---+---+
/     |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+------------------+---+---+
|         m        |   |   |
+------------------+---+---+
/                    \
+----+--------+---+                      +------+---+---+
|  e |   g    |   |                      |  t   |   |   |
+----+--------+---+                      +------+---+---+
/     |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


insert "i":
+------------------+---+---+
|         m        |   |   |
+------------------+---+---+
/                    \
+----+--------+---+                      +------+---+---+
|  e |   g    |   |                      |  t   |   |   |
+----+--------+---+                      +------+---+---+
/     |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h | i |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

insert "k":
+----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| i | k |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

insert "l":
+----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| i | k | l |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                                             +------------------------------------+---+---+
|                   m                |   |   |
+------------------------------------+---+---+
/                                      \
+--------+----------+--------+                                        +------+---+---+
|    e   |     g    |    i   |                                        |   t  |   |   |     =>
+--------+----------+--------+                                        +------+---+---+
/         |          |         \                                       /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| i | j |   |->| k | l |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+-------------------------+-----------------------------+---+
|             g           |            m                |   |
+-------------------------+-----------------------------+---+
/                          |                              \
+------+---+---+                  +--------+--------+---+                  +------+---+---+
|  e   |   |   |                  |    i   |    k   |   |                  |   t  |   |   |
+------+---+---+                  +--------+--------+---+                  +------+---+---+
/        \                        /         |         \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| i | j |   |->| k | l |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


## 删除

B+树如下：

                                             +----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| i | k | l |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                                             +----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| k | l |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                                             +----------------------+---+---+
|           m          |   |   |
+----------------------+---+---+
/                        \
+--------+----------+--------+                          +------+---+---+
|    e   |     g    |    i   |                          |   t  |   |   |    =>
+--------+----------+--------+                          +------+---+---+
/         |          |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->|   | h |   |->| k | l |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+--------------+---+---+
|       m      |   |   |
+--------------+---+---+
/                \
+--------+--------+---+                  +------+---+---+
|    e   |    g   |   |                  |   t  |   |   |
+--------+--------+---+                  +------+---+---+
/         |         \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| h | k | l |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                                      +--------------+---+---+
|       m      |   |   |
+--------------+---+---+
/                \
+--------+--------+---+                  +------+---+---+
|    e   |    g   |   |                  |   t  |   |   |   =>
+--------+--------+---+                  +------+---+---+
/         |         \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| h | k | l |->| m | p |   |->| t |   |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+------------------+---+---+
|         m        |   |   |
+------------------+---+---+
/                    \
+--------+--------+---+                      +------+---+---+
|    e   |    g   |   |                      |      |   |   |   =>
+--------+--------+---+                      +------+---+---+
/         |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| h | k | l |->| m | p | t |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+----------+---+---+
|     g    |   |   |
+----------+---+---+
/            \
+------+---+---+              +------+---+---+
|   e  |   |   |              |   m  |   |   |
+------+---+---+              +------+---+---+
/        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| h | k | l |->| m | p | t |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                           +----------+---+---+
|     g    |   |   |
+----------+---+---+
/            \
+------+---+---+              +------+---+---+
|   e  |   |   |              |   m  |   |   |    =>
+------+---+---+              +------+---+---+
/        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->|   | f |   |->| h | k | l |->| m | p | t |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+------------+--------+---+
|      g     |   m    |   |
+------------+--------+---+
/             |         \
+---+---+---+  +---+---+---+  +---+---+---+
| b | d | f |->| h | k | l |->| m | p | t |
+---+---+---+  +---+---+---+  +---+---+---+


## 其它

B+ 树和 B- 树最大的不同点是：B- 树的关键字和记录是放在一起的，叶子节点和非叶子节点中都同时包含关键字和记录；B+ 树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。在 B- 树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而 B+ 树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看 B- 树的性能好像要比 B+ 树好，而在实际应用中却是 B+ 树的性能要好些。因为 B+ 树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比 B- 树多，树高比 B- 树小，这样带来的好处是减少磁盘访问次数。尽管 B+ 树找到一个记录所需的比较次数要比 B- 树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中 B+ 树的性能可能还会好些，而且 B+ 树的叶子节点使用指针连接在一起，方便顺序遍历（例如查看一个目录下的所有文件，一个表中的所有记录等），这也是很多数据库和文件系统使用 B+ 树的缘故。

## 参考资料

1. 巧啊。。。我这两天正好在看原来那个数据库书……刚好看到B+树。。。

2. 那啥。。。删除操作那一部分，删元素x的时候，按数据库书上的那个算法，就把t左边那个指针和m都移到存e、g那个结点了，这样e、g、m三个元素就成了新的根，可以减少一层。前面插入操作有一步我按书上的算法出来的树结构也有点不同，但是B+树的性质都是满足了的…………

1. ou说道：

这是分裂/合并策略的问题……插入的时候节点满了就直接分裂，而没有检查是否可以把部分元素挪兄弟节点中；而删除的时候如果节点元素个数不满足(m/2)的条件会先检查兄弟节点，如果兄弟节点元素个数满足(m/2)就从兄弟节点借一个节点而不进行合并……

最后结果不一定完全相同吧，性质满足了就行

3. CharlesLeo说道：

讲得非常棒，感谢分享

4. chang说道：

删除x的时候，是否可以将e g m 同时合并成根节点？

1. ou说道：

可以，只要判断下这三个节点是否能够合并就行，不过也要考虑合并后再插入数据会造成新一轮的节点分裂。这篇博客只写了基本操作，生产环境中还有很多优化的地方。