# B- 树

1972 年 R. Bayer 和 E. McCreight 的论文（参考资料 [1]）提出了 B- 树。B- 树是一棵平衡树，与一般的平衡二叉树（AVL，红黑树等）不同的是，B- 树的每个节点最多可以拥有 m（m>=2）个元素，（m+1）个子节点，并且所有的叶子节点位于同一层。B- 树的查找和插入的时间复杂度和二叉树一样，都是 O(logn)，但因为每个节点保存的元素比较多（一般是几十个到几百个之间），树的高度比一般的二叉树要小很多，访问硬盘次数更少，在数据不能全部加载到内存的时候比一般的二叉树效率要好。

## 定义

• 每个节点最多有 2n+1 个元素；
• 每个非叶子节点（根节点除外）至少有 n+1 棵子树；
• 如果根节点不是叶子节点，则至少有 2 棵子树；
• 一个有 k 棵子树的非叶子节点有 k-1 个元素，按升序排列；
• 所有叶子节点位于同一层；
• 某个元素的左子树中的元素都比它小，右子树的元素都大于它（不存在相等的情况）。

                                        +-------------------------+-------------------------+---+
|             i           |            p            |   |
+-------------------------+-------------------------+---+
/                          |                          \
+---------+---------+---+                   +-------+---+---+                   +---------+---------+---+
|    d    |    g    |   |                   |   m   |   |   |                   |    t    |    w    |   |
+---------+---------+---+                   +-------+---+---+                   +---------+---------+---+
/          |          \                     /         \                         /          |          \
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
| a | b | c |   | e | f |   |   | h |   |   |   | j | k | l |   | n | o |   |   | q | s |   |   | v |   |   |   | x | y | z |
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+


## 查找

B- 树的 key 是唯一的。假设要查找字符“i”，经过比较在根节点就找到了“i”的位置，这时就可以直接把该元素返回，而不需要继续往下查找。

## 插入

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


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


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


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


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

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


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

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

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

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


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

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

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

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


                                      +-----------------------+---------------------------+---+
|             i         |              p            |   |
+-----------------------+---------------------------+---+
/                        |                            \
+--------+------------+---+                  +------+---+---+              +------+---+---+
|    e   |      g     |   |                  |   m  |   |   |              |   t  |   |   |
+--------+------------+---+                  +------+---+---+              +------+---+---+
/         |             \                    /        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |  | f |   |   |  | h |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


## 删除

                                      +-----------------------+---------------------------+---+
|             i         |              p            |   |
+-----------------------+---------------------------+---+
/                        |                            \
+--------+------------+---+                  +------+---+---+              +------+---+---+
|    e   |      g     |   |                  |   m  |   |   |              |   t  |   |   |
+--------+------------+---+                  +------+---+---+              +------+---+---+
/         |             \                    /        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b |   |   |  | f |   |   |  | h |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                           +-------------------+--------------------+---+
|           i       |           p        |   |
+-------------------+--------------------+---+
/                    |                     \
+------+---+---+              +------+---+---+              +------+---+---+
|  g   |   |   |              |   m  |   |   |              |   t  |   |   |
+------+---+---+              +------+---+---+              +------+---+---+
/        \                    /        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | e |   |  | h |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                           +-------------------+--------------------+---+
|           i       |           p        |   |
+-------------------+--------------------+---+
/                    |                     \
+------+---+---+              +------+---+---+              +------+---+---+
|  g   |   |   |              |   m  |   |   |              |   t  |   |   |      =>
+------+---+---+              +------+---+---+              +------+---+---+
/        \                    /        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | e |   |  | h |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+-----------+---+---+
|     p     |   |   |
+-----------+---+---+
/             \
+------------+----------+------------+               +------+---+---+
|      g     |     i    |      m     |               |   t  |   |   |      =>
+------------+----------+------------+               +------+---+---+
/             |          |             \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | e |   |  | h |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+-----------+---+---+
|     p     |   |   |
+-----------+---+---+
/             \
+------------+----------+------------+               +------+---+---+
|      e     |     i    |      m     |               |   t  |   |   |
+------------+----------+------------+               +------+---+---+
/             |          |             \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b |   |   |  | g |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


                                      +--------------+---+---+
|       p      |   |   |
+--------------+---+---+
/                \
+--------+------------+---+                  +------+---+---+
|    i   |      m     |   |                  |   t  |   |   |
+--------+------------+---+                  +------+---+---+
/         |             \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| e | g |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


delete "e":
+--------------+---+---+
|       p      |   |   |
+--------------+---+---+
/                \
+--------+------------+---+                  +------+---+---+
|    i   |      m     |   |                  |   t  |   |   |
+--------+------------+---+                  +------+---+---+
/         |             \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| g |   |   |  | k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

delete "g":
+--------------+---+---+
|       p      |   |   |
+--------------+---+---+
/                \
+--------+------------+---+                  +------+---+---+
|    k   |      m     |   |                  |   t  |   |   |
+--------+------------+---+                  +------+---+---+
/         |             \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| i |   |   |  | l |   |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

delete "i":
+----------+---+---+
|     p    |   |   |
+----------+---+---+
/            \
+------+---+---+              +------+---+---+
|   m  |   |   |              |   t  |   |   |
+------+---+---+              +------+---+---+
/        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


          +------------+----------+------------+
|     p      |     m    |      t     |
+------------+----------+------------+           =>
/             |          |             \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| k | l |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

+------------+----------+------------+
|     p      |     m    |      t     |
+------------+----------+------------+
/             |          |             \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| l |   |   |  | n | o |   |  | q | s |   |  | v | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+


## 参考资料

[1] Organization and Maintenance of Large Ordered Indexes
[2] B-tree
[3] 算法导论（第二版），（美）Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein 著，潘金贵，顾铁成，李成法，叶懋 译。