树
二叉查找树（BST）
概念
二叉查找树实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据均小于或等于根节点的数据，右子树上所有的结点的数据均大于根节点的数据
平衡二叉树（AVL树）
概念
本质上还是二叉查找树，但是需要满足平衡的要求，即对任意节点来说，其左子树与右子树的高度之差的绝对值不超过1
保持平衡
| 插入方式 | 描述 | 旋转方式 |
|---|---|---|
| LL | 在a的左子树根节点的左子树上插入节点而导致破坏平衡 | 右旋转 |
| RR | 在a的右子树根节点的右子树上插入节点而导致破坏平衡 | 左旋转 |
| LR | 在a的左子树根节点的右子树上插入节点而导致破坏平衡 | 先左旋后右旋 |
| RL | 在a的右子树根节点的左子树上插入节点而导致破坏平衡 | 先右旋后左旋 |
当一颗AVL因为插入后变得不平衡了
这样子就失衡了，所谓右旋，就是将这个AVL树，从最靠近插入节点的失衡处，通过往右子树调整，使整棵树的每个节点的平衡因子变为正常
B树
概念
B树又名平衡多路查找树（查找路径不只有两个）
规则
排序方式：所有节点关键字递增排序，遵循左小右大原则
子节点数：非叶节点的子节点数 > 1，且 <= M，且 M >= 2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M = M路，当M=2则是二叉树，M=3则是3叉
关键字树：枝节点的关键字数量大于等于$ceil(m/2)-1$ 且小于等于M-1个
所有叶子节点均在同一层、叶子节点除了包含关键字和关键字记录的指针外也有指向其子节点的指针只不过指针地址都为null对应下图最后一层节点的空格子
查询过程
如上图我要从上图中找到E字母，查找流程如下
获取根节点的关键字进行比较，当前根节点关键字为M，E < M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
拿到关键字D和G，D < E < G 所以直接找到D和G中间的节点；
拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
插入
先插入 3、8、31、11
再插入23、29
再插入50、28
删除
特点
B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是以块的形式，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读出来）把节点大小限制和充分使用在磁盘块大小范围；把树的节点关键字增多后树的层级比原来二叉树少了，减少数据查找的次数和复杂度
B+ 树
概念
B+树是B树的一个升级版
规则
B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加
B+树的叶子节点保存了父节点所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取得到，所以每次查询次数都是一样的
B+树的叶子节点的关键字按从小到大排序，左边结尾数据都会保存右边节点开始数据的指针
特点
因为非叶子节点不存储记录的指针，所以每个节点能存储的关键字更多，树的层级更少所以查询数据更快
B+树的记录都在叶子节点上所以查询速度更稳定
B+树天然具备排序功能并且全节点遍历更快
B*树
特点
- B*树的节点具有指向兄弟节点的指针，当节点满了可以将记录转移到兄弟节点处
