B+树更加适合在区间查询的情况，B+树常用于数据库索引，而B树则常用于文件索引。
B树：
树的总体结构：
image.png
特点：
- 叶节点在同一层
- 每个节点内的关键字按从小到大排列
- B树的高度位于[ logm(n+1)，log[m/2](n+1)/2+1 ]之间
注: 前者按照满m叉算，后者按照根节点2叉，其他[m/2]叉算 - 数据存储在所有非叶节点中，叶节点用NULL表示占一层，但是不算高度。
- 根节点最多两个子树，其他为n个。
- 根结点中关键字的个数为[ 1，m-1 ]，子树范围[ 2，m-1 ]；其他非叶节点关键字范围[ [m/2]-1，m-1 ]，子树范围[ [m/2]，m-1 ]
节点处结构：（P为指针，K为值）
image.png
查找：
- 在B树中找到对应节点（先从磁盘中读取树的root节点到内存中，再对树进行遍历，边遍历边把指针对应的新节点读取到内存中）
- 确定范围后根据节点指针读取节点内的关键字K1，K2，然后找到关键字。
- 磁盘IO的次数与最后的深度一般1:1，在内存中还会单独有匹配。
插入：
插入但不溢出：（插入后<=m-1）m表示最大叉数
image.png
插入但溢出然后拆散：（插入前==m-1）
左半部分留在原地
中间的合并进父节点
-
右半部分放入同一级的新节点中
image.png
删除：
简单删除：（删除后>=[m/2]-1）
image.png
删除但是节点过少合并：
-
从父节点调剂一个过来，然后拿兄弟节点补双亲（移动前其他节点>[m/2]-1），因为要保持中序遍历次序不变（有点像BST）。
image.png -
兄弟靠不上怎么办？在原位置跟右兄弟节点与双亲节点中的第一个关键字合并，若双亲节点被掏空为0就把双亲节点位置替换成自己。
image.png
B+树：
特点：
- 每个节点中指针数量与关键字数量一样
- 所有数据记录在叶节点中，非叶节点只负责做索引不含存储地址，索引项只含子树最大关键字和指向子树的指针，关键字个数位于[[m/2]，m]之间。
- B+树有两个头指针，一个指向根节点，一个指向关键字最小的节点。
- 相邻叶节点会用指针串起来。
image.png
