B与B+树

B+树更加适合在区间查询的情况，B+树常用于数据库索引，而B树则常用于文件索引。

---

B树：

树的总体结构：

image.png

特点：

1. 叶节点在同一层
2. 每个节点内的关键字按从小到大排列
3. B树的高度位于[ logm(n+1)，log[m/2](n+1)/2+1 ]之间
   注: 前者按照满m叉算，后者按照根节点2叉，其他[m/2]叉算
4. 数据存储在所有非叶节点中，叶节点用NULL表示占一层，但是不算高度。
5. 根节点最多两个子树，其他为n个。
6. 根结点中关键字的个数为[ 1，m-1 ]，子树范围[ 2，m-1 ]；其他非叶节点关键字范围[ [m/2]-1，m-1 ]，子树范围[ [m/2]，m-1 ]

节点处结构：（P为指针，K为值）

image.png

---

查找：

1. 在B树中找到对应节点（先从磁盘中读取树的root节点到内存中，再对树进行遍历，边遍历边把指针对应的新节点读取到内存中）
2. 确定范围后根据节点指针读取节点内的关键字K1，K2，然后找到关键字。

• 磁盘IO的次数与最后的深度一般1:1，在内存中还会单独有匹配。

---

插入：

插入但不溢出：（插入后<=m-1）m表示最大叉数

image.png

插入但溢出然后拆散：（插入前==m-1）

1. 左半部分留在原地

2. 中间的合并进父节点

3. 右半部分放入同一级的新节点中

   
   image.png

---

删除：

简单删除：（删除后>=[m/2]-1）

image.png

删除但是节点过少合并：

1. 从父节点调剂一个过来，然后拿兄弟节点补双亲（移动前其他节点>[m/2]-1），因为要保持中序遍历次序不变（有点像BST）。

   
   image.png

2. 兄弟靠不上怎么办？在原位置跟右兄弟节点与双亲节点中的第一个关键字合并，若双亲节点被掏空为0就把双亲节点位置替换成自己。

   
   image.png

---

B+树：

特点：

1. 每个节点中指针数量与关键字数量一样
2. 所有数据记录在叶节点中，非叶节点只负责做索引不含存储地址，索引项只含子树最大关键字和指向子树的指针，关键字个数位于[[m/2]，m]之间。
3. B+树有两个头指针，一个指向根节点，一个指向关键字最小的节点。
4. 相邻叶节点会用指针串起来。

image.png