回顾二叉查找树(又叫二叉排序树BST)：
二叉排序树在查找时每次都把范围缩小一半吧。。。。。。
5叉排序树：
结构体Node节点中的字段有keys[4]即最多4个关键字，child[5]即最多5个孩子，num记录节点中的关键字个数，节点里的关键字是有序的，要么递增要么递减，紫色节点是失败节点。如果节点中最少有1个关键字，则有2个分叉，有最多4个关键字，则有5个分叉，如下左图2中第2层有36和45这俩关键字，就分成了(22,36),(36,45)(45,+∞)三个区间，即三个分叉。如第3层13、15下的紫色节点，其父节点(5,11)所指向的三个分叉的区间范围分别是(-∞,5)二这个分叉即区间上实际就1和3关键字，(5,11)分叉上有6、8、9关键字，(11,22)分叉上有13、15关键字，则15后边的分叉指向的紫色失败区间范围应该是(15,22)。。。。第三层40左边的分叉指向的紫色失败范围应该是(36,40)，因为每个节点中的关键字都有序，而40所在的节点的范围应该是(36,45)，但是实际40节点上的关键字只有40、42，所以紫色节点上少的关键字应该是(37,38,39)
5叉排序树查找：
查找9目标元素成功：先从根节点22开始，9<22，从22的左边分叉路线开始找，然后再从左到右顺序查找左边分叉路线指向的节点中的关键字依次进行对比（因为节点内的元素都是有序的，所以在节点中的关键字个数较多的情况下，查询节点内的关键字也可采用折半查找），5<9，则继续往右找，9<11，则9肯定在11的左边的分叉指向的节点中，然后再在11左边分叉指向的节点的关键字中顺序查找，6<9下一个，8<9下一个，9==9，查找成功
查找41目标元素失败：先从根节点22开始，22<41，则让指针右移，但是该节点上已经没有其他关键字，所以如果41存在的话，只能是从指针指向的22的右边分叉路线开始找，即让指针移动到22右边指针指向位置，即顺序从左到右查找该分叉路线指向的关键字节点，36<41，则继续往右找，41<45，则41肯定在45左边的指针36指向右边的分叉指向的节点中，然后再在36右边分叉指向的节点的关键字中顺序查找，40<41则指针右移继续往右找，42>41，则让指针移到到42左边的指针指向的位置，即紫色节点位置，即查找失败，紫色失败节点即为虚拟的NULL节点
如何保证5叉排序树查找效率====》策略1：
保证查找效率即让树变低，尽量少的查更多层节点，树变低就让每个节点的关键字足够多，则在m叉查找树中，规定除了根节点外，任何节点至少有m/2向上取整个分叉(下层节点个数)，即至少含有m-2向上取整-1个关键字(当前节点上的关键字个数)。如果m=5对于5叉排序树，则除了根节点外，则任何节点至少含有3个分叉，2个关键字。
为啥除了根节点之外：比如开始在构造5叉查找树的时候，只有1个根节点1个关键字，这1个根节点最多只有2个分叉，所以不可能在5叉查找树中保证根节点也至少有3个分叉，2个关键字，所以要把根节点排除在外。
多叉查找树情况下的不平衡：
如下，每个节点上有5个child即5叉查找树，虽然满足了除了根节点其他任一个节点上至少有2个关键字和3个分叉，但是该5叉查找树也有优秀，因为各个子树的高度相差很大，导致5查查找树的高度很高，高度高会导致查找的时候查找很多层的节点，导致查找效率降低(可能吧。。。。。)。如根节点22的一个指向紫色节点的子树的高度为1,（5,11）子树的高度为4(4还是2啊？？？)，(5,11)的子树有2个紫色节点，还有(1,3)节点，(1,3)节点还有子树指向紫色节点
多叉查找树情况下的保证平衡===》策略2：
在多叉查找树中，规定任何一个节点，其所有子树的高度都相同。 (二叉排序树中是规定左右子树高度差不超过1)，所有的节点的子树都相同导致的结果是所有的失败节点即叶子节点都出现在最下层
B树(多路平衡查找树)：
多路：每个节点可能有多个分叉出现
平衡：每个节点的所有子树的高度都相同，即绝对平衡，各个子树的高度都没有高度差(avl平衡二叉树的左右子树的高度差不超过1)
B树的阶：找节点中具有最多分叉的，分叉是几就是几阶B树，就是几阶加了2个策略来保证查找效率的查找树(如5叉排序/查找树，加了2个粗略来保证查找效率后，就变成了5阶B树)
B树特性：
1.树中每个节点最多有m个子树(即最多m个分叉，几个最多分叉叫几阶B树)，最多有m-1个关键字
2.若根节点不是终端节点，则至少有2个子树。(B树有绝对平衡，即每个节点的各个子树的高度都相同，假如说这个根节点不是终端节点，它只有一个子树，则这个子树的高度必定>=1，但是另外一个子树的高度==0，即不满足绝对平衡，则如果根节点不是终端节点，它一定至少有2个子树)
3.除根节点外，所有的非叶子节点至少有m/2向上取整个子树，即至少含有m/2向上取整-1个关键字(因为绝对平衡吗.......)
4.每个非叶子节点，有字段n记录当前该节点下一共有几个关键字，如果当前节点有k1、k2、k3....等n个关键字，则有n+1个指针(分叉)，且关键字有序(有序是可为递增也可为递减)，Pi所指的子树节点中的所有关键字都>Ki，P(i-1)所指子树节点中的所有关键字都<Ki
5.所有的叶子节点即为空指针节点即查找失败的节点都在最下一层(因为绝对平衡)
注意每个节点的子树数就是每个节点的分叉数
B树最小高度：
B树高度一般不包括叶子节点这一层
每个节点最多有m-1个关键字，每个节点最多有m个分叉，第一层有1个关键字，然后发出m个分叉即第二层有m个节点，m个节点再发出m个分叉，即第三层有m²个节点，第3层再发出m个分叉即m个节点，即第4层有m³个节点。。。。。。。。如果B树高度为h，则最多会有m的h-1次方个节点，则高度为h的情况下，关键字最多会有(m-1)(1+m+m²+m³+.......+m的h-1次方)=m的h次方-1>=n即h>=logm(n+1)
B树最大高度：
从节点个数入手求最大高度：
让B树的高度高则让各层分叉(或者说子树/节点)尽可能的少，根节点只有2个分叉，其他每个节点至少有m/2向上取整个分叉(几个分叉代表有几个子树，即代表有几个节点)，则各层节点至少有：第一层有1个节点，第2层有2个节点，第3层有2(m/2向上取整)个节点，第4层有2(m/2向上取整)²个节点，第5层有2(m/2向上取整)³个节点。。。。。。第h层有至少2(m/2向上取整)的h-2个节点
叶子节点不在高度h包括范围内，即叶子节点所在第h+1层，第h+1层有至少2(m/2向上取整)的h-1个节点
B树中的n个关键字相当于把(-∞，+∞)切分成了n+1块，这n+1块就代表了n+1个失败的叶子节点，则如果B树中有n个关键字，那B树中一定有n+1叶子节点。
则综上，n+1>=2(m/2向上取整)的h-1个节点，则h求值如下倒数第2张图
从关键字个数入手(最后一张图)求最大高度：
设k=m/2向上取整
第一层1个节点，1个关键字
第2层2个节点，2(k-1)个关键字(因为除了根节点之外，每个节点的关键字个数至少为k-1，每个节点的分支/子树节点至少为k)
第3层2K个节点，2k(k-1)个关键字(因为除了根节点之外，每个节点的关键字个数至少为k-1)
第4层2K²个节点，2K²(k-1)个关键字(因为除了根节点之外，每个节点的关键字个数至少为k-1)
........
第h层2K的h-2次方个节点，2K的h-2次方(k-1)个关键字(因为除了根节点之外，每个节点的关键字个数至少为k-1)
则h层至少的关键字总数为以上从第1层关键字个数求和到第h层，即1+2(k-1)+2k(k-1)+2K²(k-1)+....=1+2(k的h-1次方-1)个关键字 <=n，然后求出h的最大值
知识回顾：
。。。。。。。老天救救孩子。。。。。。。。。
