B树(B-树)

1）B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树和红黑树，都能在磁盘I/O操作数方面要做过优化，但是B树的搜索速度会比红黑树快。

2）现在许多数据库系统使用B树或者B树的变种(B 树和B*树)来存储信息。B树用的比较普遍，B树和红黑树相比较，就是子树多点 即路数多，子树越多表示数的高度越低，搜索效率越高，当然如果路数太多就可能变成一个有序链条了。所以当然不可能使得路数无限大。

可以认为红黑树是一个是个高瘦子，而B树是一个矮胖子。

3）B树多用于做文件系统的索引。

1）前言：上取正“⌈ ⌉”和下取正“⌊ ⌋” 拿3.5做例子,下取整就等于3,上取整就等于4，

2）当然可以使用 这些函数 ceil函数（向上取整）；floor函数（向下取整）；round函数（四舍五入）；

3）一颗m阶的B树或空树：

（0）根节点至少有两个孩子。

（1）每个非根节点的孩子节点个数满足：⌈m/2⌉ <= x <= m (x表示孩子节点个数)。

（2）每个非根节点的关键字个数满足：⌊m/2⌋ <= x <= m-1。

（3）每个节点的关键字Ki(i=1...n) 由小到大排序 。

（4）每个节点都有这些数据(n,P0,K1,P1,K2,P2,…,Kn,Pn) ,P是父指向值的指针,而关键字都夹在指针之间，比关键字多一个数量，而第一个n是标示关键字个数的值。

（5）所有的外部节点都在同一层，所有节点(包括外部节点)的平衡因子为0，而在计算高度的时候 外部节点也要计算(这点比较特殊 因为一般是从叶子节点开始数的，外部节点也是虚拟节点，其实虚拟节点也叫失败节点，没有任何的关键字和指针)；

（6）所有的节点关键字个数总和=所有虚拟节点个数 1；

（7）关键字可以认为是key ，数据是还有value,它们是一个对应的关系。

7）专业术语：在上图中key为3的左孩子为节点是1 2 ，右孩子的的节点是4 5；

8）同理 上图中key为6的左孩子节点是4 5，右孩子的节点是7 9；

1）前言：理论可能抽象 尽量看案例 才能理解 ：

（1）插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

2）插入操作会进行一下步骤：

（1）根据要插入的key的值，找到叶子结点并插入。

（2）插入后，判断当前结点key的个数是否小于等于m-1，若满足则结束。否则就要进行第(3)步。

（3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

3）案例一：下面以原图为5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key。

（1）在空树中插入39，可以看出图中 此时根结点就一个key，此时根结点也是叶子结点

（2）继续插入22，97和41

可以看出图中 根结点此时有4个key

（3）继续插入53

根结点此时有4个key 插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。

当阶数m为“偶数”时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

（4）依次插入到左子树 13，21，40，同样会造成分裂，结果如下图所示。

4）案例二 ：

下面以原图阶为5的B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key

（1）插入key值为26的记录，插入后的结果如下图所示。

（2）当前结点需要以27为中心分裂,并向父结点进位27,然后当前结点指向父结点，结果如下图所示

（3）进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

（4）分裂后当前结点指向新的根，此时无需调整。

1）从非叶子节点Q 开始删除经历的步骤：

非叶子节点Q有子节点Q1和Q2，而Q1和Q2是兄弟节点，m是阶数。

（1）如果当前需要删除的key位于Q，则用后继key(比如27后续是28,29等)覆盖要删除的key，然后在后继key所在的Q2删除该后继key。

（2）如果上面Q删除后 它的Q2的key个数大于等于Math.ceil(m/2)-1，则结束删除操作。否则就执行第3步

（3）基于上面Q的key删除后 如果它的Q1key个数大于Math.ceil(m/2)-1，则Q中的key下移到Q2，Q1中的一个key上移到父结点，此时删除操作结束。否则Q1的key个数小于Math.ceil(m/2)-1 则执行步4

（4）基于Q的key删除后 Q1的key不足 所以只能让Q的key下移和Q1与Q2的key全部合并，成为一个新的结点，并且Q重新指向合并的新节点

2）从叶子节点Q2开始删除经历的步骤：

非叶子节点Q有子节点Q1和Q2，而Q1和Q2是兄弟节点，m是阶数。

（1）如果删除后Q2的key个数大于等于Math.ceil(m/2)-1， 则结束删除操作。否则就执行第2步

（2）基于上面步骤 如果它的Q1的key个数大于Math.ceil(m/2)-1，则Q中的key下移到Q2，Q1中的一个key上移到父结点，此时删除操作结束。否则Q1的key个数小于Math.ceil(m/2)-1 则执行步3

（3）基于上面的步骤 Q1的key不足 所以只能让Q的key下移和Q1与Q2的key全部合并，成为一个新的结点，并且Q重新指向合并的新节点

3）案例一 从非叶子节点开始删除：

（1）下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key。

这里的案例将会经历 1）中定义的（1-3），(4)没有经历

（2）原始状态

（3）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28(原27)的右孩子结点中删除28。删除后的结果如下图所示。

（4）删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

4）案例二 叶子节点开始删除：

这里的案例将会经历 2）中定义的（1-3）

（1）原图阶为5的图开始

（2）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

（3）同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟结点合并，合并后的指向当前结点的指针就指向了父结点。

（4）同理，对于当前结点而言只能继续合并了，最后结果如下所示。

（5）合并后结点当前结点满足条件，删除结束。

1）聚集索引就是如上面的图中，索引和数据在同一个节点；

2）而非聚集索引就是，索引和数据不再同一个节点；