一、平衡二叉树
基于二分法策略提高数据查找速度的二叉树 ps: 分法通常要求目标数组中的数据是有序排列
旋转来保持平衡，若部分加载到内存，无法旋转。其次平衡二叉树高度相对较大为 log n（底数为2），逻辑上很近的节点实际可能非常远，无法很好利用磁盘预读（局部性原理），在db和文件系统上的被 pass
查询性能和树的层级（h高度）成反比，保证平衡降，算法机制实现节点数据结构的平衡，实现算法的有比如AVL、Treap、红黑树，
特点：
（1）非叶子节点最多有两个子节点；
（2）非叶子节值大于左边子节点、小于右边子节点；
（3）树的左右两边的层级数相差不大于1;（避免成线性链表，影响查询效率）
（4）没有值相等重复的节点;
二、B树(B-tree)
1、B-树由来
（1）传统平衡二叉树，数据大查询性能一般，如 AVL 树，红黑树等。因为内存不够，只放磁盘上，要的才加载到内存中。一般内存访问时间约50 ns，磁盘10 ms。速度差5 个数量级，大部分时间会阻塞在磁盘 IO 上
（2）B-特点：节点关键字增多，层级少，减少查找次数和复杂度;
充分利用磁盘块原理（磁盘数据用块形式存储，每块4K，每次IO同块一次性读）限制节点大小在磁盘快范围
（3）从“迎合”磁盘角度来看B-树设计
快速索引减少磁盘 IO 次数：1.区间越多，定位越精确。2.新建节点时，直接申请页大小空间（磁盘按 block 分的，一般为 512 Byte。3.磁盘 IO 一次读若干个 block，称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐，实现一个节点一次 IO
2、结构
多叉树，平衡多路查找树，数据库索引大量使用B树和B+
（1）节点关键字是按递增次序排列，左小右大
（2）子节点数量m>=2，空树除外
（3）非根节点关键字数量大于等于ceil(m/2)-1且小于等于m-1个；（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
（4）非叶节点有N个子节点，关键字数等于N-1
（5）所有叶子节点在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
3、B树查询流程：
找E字母：
（1）根节点关键字比较，当前根节点关键字为M，E要小于M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
4、B树的插入节点流程
3、8、31、11、23、29、50、28 构建出5阶树
（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2） -1小于等于5-1（关键字数小于cei(5/2) -1就要进行节点合并，大于5-1就要进行节点拆分,非根节点关键字数>=2）；
（2）右边节点>节点本身>左边节点大
5、B树节点的删除
规则：
（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1，小于等于5-1，非根节点关键字数大于2；
（2）右边节点>节点本身>左边节点大
（3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
三、B+树
B树升级版，充分节点空间，查询速度更稳定，完全接近于二分法查找。
1、特点
1）查询数据更快；缓存命中率高
2）适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确：
ps：B优点，经常访问根节点附近，非叶子节点存关键字，比B+树快。
2、时间复杂度（和b树不同）
B+树内节点不存储数据，叶节点固定为 log n。B-查询不固定，与 key 在树中的位置有关，最好O(1)
3、结构（和b树不同）
（1）B+跟B不同，非叶子节点不保存关键字指针，只数据索引(数据的文件地址，按顺序)，非叶子节点保存关键字增加；
因为InnoDB 中页默认16KB，存更多键值，相应树阶更大，更矮更胖，磁盘IO 少，效率快：如一个节点存储 1000 键值，3 层可1000×1000×1000=10 亿数据。根节点是常驻内存，查找 10 亿， 2 次磁盘 IO。
（2）叶子节点保存父节点关键字记录指针，每个叶子节点关键字从小到大构成有序链表，所有数据地址必须要到叶子节点才能获取到，每次数据查询次数都一样；
（3）节点数(非叶子)=关键字数（另一种算法,关键字数(非叶节点)=子节点数-1，数据排列结构不一样，原理一样）
查找过程
select * from user where id>=18 and id <40
①页 1 内存中了，直接读。找到 id=18 的键值，根据指针 p2，定位到页 3。
②拿着 p2 指针去磁盘中读页 3，找到键值 18，拿到p1，定位到页 8。
③再去磁盘中将页 8 读到内存，页中键值是按照顺序放，二分法定位到18，一直找到22 页 8 中没有，拿 8 中 p 指针读页 9
④直到页 12 加载到内存，发现 41 大于 40，终止。总共 12 条记录：
(18,kl), (19,kl), (22,hj), (24,io), (25,vg) , (29,jk), (31,jk) , (33,rt) , (34,ty) , (35,yu) , (37,rt) , (39,rt) 。
4、B*树
B+树变种，不同：
（1）初始化容量变大，节点空间使用率高：B+树初始化关键字个数cei(m/2)，b*树（cei(2/3*m)）
（2）分解次数变少：B+树节点满分裂，B*树检查兄弟节点是否满（每个节点都有指向兄弟指针），兄弟节点满，从当前节点和兄弟节点各拿出1/3数据创建新节点
5、 总结
相同：都是采用二分法和数据平衡策略，提升查找速度；
不同：磁盘空间利用
通过IO从磁盘读取数据，一步步的演变，树层级减少快速
附（二分法查找）：二分法查找原理 - 知乎专栏
附（B、B+、B*树）：从B树、B+树、B*树谈到R 树
附（B、B+、B*树）：end's coding life
附：B树和B+树的插入、删除图文详解 - nullzx - 博客园
https://www.cnblogs.com/zhuyeshen/p/12082839.html
https://www.cnblogs.com/kaleidoscope/p/9481991.html
