B-树

B树是一种类似于红黑树的树，但并非是二叉树，是多叉树，假设一个节点有n个孩子，那么，该节点将存储n-1个关键字，这些关键字就是孩子们之间的分割线，通过比对这n-1个关键字，即可知道数据是在哪个孩子里面。

由于机械硬盘的随机读取速度非常慢，故希望能在一次读取中读取多个数据，B树就可以优化读取的这一部分，即IO部分。另外，为了保证少读取几次，要使得B树的高度尽可能小。

在电脑中，主存的大小一般小于磁盘大小。对于存储在硬盘上的一棵超大的B树，需要分次读取。一般来说，这颗B树的每一个节点的大小应和主存大小差不多，使得能够最大的减少B树的高度。此处的读取是连续读取。

每一个节点内部是否可以用链表？

卫星数据

一般来说，所有对数据的整体操作，都会依赖于关键字，数据依附于关键字而存在，故被称为卫星数据。

节点属性

1. 关键字的个数
2. 关键字
3. 关键字的指针
4. 是否是叶节点

重要性质

存在一个最小度数t，使得除根节点外的节点的子节点个数$n\ge t-1且n\le 2t-1$。

高度

$h\le log_t\frac{n-1}{2}$

搜索

• B树的根结点始终在主存中，这样无需对根做DISK-READ操作；然而，当根结点被改
  变后，需要对根结点做一次DISK-WRITE操作。
• 任何被当做参数的结点在被传递之前，都要对它们先做一次DISK-READ操作。

并不知道第二条约定是为什么而存在

和二叉搜索树差不多，每到一个节点遍历关键字，继续向下，直到存在或者说是叶节点。

插入

但首先需要特殊创建一个叶节点来作为根节点。

接着，插入时B树并不像其他的树一样建立一个新的节点，不然就违反B树的性质了。B树扩张的方式是分裂节点，正如前所述，B树的节点是有一个最大的子节点数上限的，当一个节点到了这个上限，就会将其split成两个$t-1$大小的节点，而其父节点的关键字也会+1。然而其父节点也可能会因为这+1而需要分裂，因此分裂的操作会在插入的时候自上而下的进行，以保证被分裂的节点的父节点并不是满的。

但是，可以发现的是，虽然分裂操作能够扩张树，但是只能水平的进行扩张，但这样还是会到极限的。此时，我们可以去思考一下，在什么样的情况下，我们会认为当前的B树快满了，需要进行纵向的扩张呢？

就是在根节点满的时候。当根节点满的时候，虽然还有一些空位，但也表明需要扩张了。有趣的是，B数的扩张并不是向下的，而是向上的，通过在根节点上再制造一个根节点使得原本的根节点成为它的孩子的方式来扩张，接着分裂原本的根节点即可。

接下来是具体插入时的操作。在碰到一个节点时，自后向前扫描，这样能够它需要插入新的节点的关键字的时候，能够顺便将后面的直接向后移一位。注意，非叶节点是不可能在插入的时候进行扩张的，当且仅当其子节点扩张的时候，它自身才会进行扩张。

删除

情况一：不是叶节点。

1. 如果该关键字前的子节点的关键字大于t-1，则将其后继替换本关键字。
2. 如果该关键字后的子节点的关键字大于t-1，则将其前驱替换本关键字。
3. 如果前后都小于t，则将其合并，此时合并所得节点的关键字数量会小于2t。

情况二：是叶节点。删除即可。

但会出现叶节点的关键字过少的问题。

1. 如果该叶节点左右有大于t-1的叶节点，则将其后继或前驱上升至父节点，父节点的关键字下降到本节点。
2. 如果该叶节点左右没有大于t-1的叶节点，则将其余其兄弟合并，此时其父节点的中间关键字需要下放。

B+树

B+树是B树的变体。

1. 其内部节点不会存卫星数据及其关键字，所有的数据都会在其子节点可以找到。
2. 而内部节点中关键字的个数不是n-1个，而是n个，其关键字为其子节点的最大值或者最小值。
3. 其叶节点之间会存在指针，从较小的叶节点指向较大的叶节点，形成了一个链表。

优点

1. 因为中间节点不会存数据，因此更加矮胖，IO次数更少。
2. 必须抵达叶节点，更加稳定。
3. 能够轻松地靠叶节点链表进行范围查询。