从二分查找法到b树系列
1、二分查找
二分查找是最基本的，后面的二叉树，平衡二叉树，B树，B+树都是基于二分查找演变而来的。
二分查找法也称为折半查找法，用来查找一组有序记录数组中某一项记录，基本思想是将记录按有序化排列（递增递减），查找过程采用跳跃方式查找，即先以有序数列的重点位置为对比对象，如果要找的元素小于该中点元素，则将待查找序列缩小为左半部分，否则右半部分。如下对5、10、19、21、31、37、42、48、50、52这10个数，要从中查找48这条记录。
从上可以看出3次就找到了48这个数，如果要是按顺序查找则需要8次。因此二分查找法的效率（平均来说）比顺序查找法要好。如下采用java递归方式完成二分查找算法，下面我用PHP来实现二分查找法
//二分查找法
function binSearch($arr,$search){
$height=count($arr)-1;
$low=0;
while($low<=$height){
$mid=floor(($low+$height)/2);//获取中间数
if($arr[$mid]==$search){
return $mid;//返回
}elseif($arr[$mid]<$search){//当中间值小于所查值时，则$mid左边的值都小于$search，此时要将$mid赋值给$low
$low=$mid+1;
}elseif($arr[$mid]>$search){//中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
$height=$mid-1;
}
}
return "查找失败";
}
//二分查找递归实现
function binSearch2($arr,$low,$height,$k){
if($low<=$height){
$mid=floor(($low+$height)/2);//获取中间数
if($arr[$mid]==$k){
return $mid;
}elseif($arr[$mid]<$k){
return binSearch2($arr,$mid+1,$height,$k);
}elseif($arr[$mid]>$k){
return binSearch2($arr,$low,$mid-1,$k);
}
}
return -1;
}
2、二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(Left Subtree)和“右子树”(Right Subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树有如下特性：
- 每个结点都包含一个元素以及 n 个子树，这里 0≤n≤2。
- 左子树和右子树是有顺序的，次序不能任意颠倒。左子树的值要小于父结点，右子树的值要大于父结点。
假如我们有一组数[35 27 48 12 29 38 55]，顺序的插入到一个数的结构中,最终的结果如下：
好了，这就是一棵二叉树啦！我们能看到，经过一系列的插入操作之后，原本无序的一组数已经变成一个有序的结构了，并且这个树满足了上面提到的两个二叉树的特性！
但是如果同样是上面那一组数，我们自己升序排列后再插入，也就是说按照[12 27 29 35 38 48 55]的顺序插入，会怎么样呢？
由于是升序插入，新插入的数据总是比已存在的结点数据都要大，所以每次都会往结点的右边插入，最终导致这棵树严重倾斜。
上图就是最坏的情况，也就是一棵树退化为一个线性链表了，这样查找效率自然就低了，完全没有发挥树的优势了呢！
为了较大发挥二叉树的查找效率，让二叉树不再倾斜，保持各科平衡，所以有了平衡二叉树！
3、平衡二叉树
概念
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。
特点
平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：
- 非叶子节点只能允许最多两个子节点存在。
- 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里 值是基于自己的算法规则而定的，比如hash值)；
平衡树的层级结构：因为平衡二叉树查询性能和树的层级(h高度)成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如AVL、Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找；
前面[35 27 48 12 29 38 55]插入完成后的图，其实就已经是一棵平衡二叉树啦。
那如果按照[12 27 29 35 38 48 55]的顺序插入一棵平衡二叉树，会怎么样呢？
这棵树始终满足平衡二叉树的几个特性而保持平衡！这样我们的树也不会退化为线性链表了！
我们需要查找一个数的时候就能沿着树根一直往下找，这样的查找效率和二分法查找是一样的呢！
一棵平衡二叉树能容纳多少的结点呢？
这跟树的高度有关系的，假设树的高度为h，那每一层最多容纳的结点数量为 2^(n-1)，整棵树最多容纳节点数为 20+21+22+…+2(h-1)。
这样计算，100w 数据树的高度大概在 20 左右，也就是说从有着 100w 条数据的平衡二叉树中找一个数据，最坏的情况下需要 20 次查找。
如果是内存操作，效率也是很高的！但是我们数据库中的数据基本都是放在磁盘中的，每读取一个二叉树的结点就是一次磁盘 IO，这样我们找一条数据如果要经过 20 次磁盘的 IO？
平衡二叉树的特点：
- 非叶子节点最多拥有两个子节点；
- 非叶子节值大于左边子节点、小于右边子节点；
- 树的左右两边的层级数相差不会大于1;
- 没有值相等重复的节点;
4、B-tree
根据上面的平衡二叉树可以得出，如果数据量大的话，查询某一条数据，会大大增加磁盘IO操作(内存数据库除外)，这样会使得性能降低，于是我们便想到是否可以把这一颗平衡二叉树压缩一下，让她的叶子节点变多一些，高度降低一些，于是就演变为了B树。虽然我矮，但是我胖。
这颗矮胖的树就是 B-Tree，注意中间是杠精的杠而不是减，所以也不要读成 B 减 Tree 了。
一棵 m 阶的 B-Tree 有如下特性：
- 每个结点最多 m 个子结点。
- 除了根结点和叶子结点外，每个结点最少有 m/2(向上取整)个子结点。
- 如果根结点不是叶子结点，那根结点至少包含两个子结点。
- 所有的叶子结点都位于同一层。
- 每个结点都包含 k 个元素(关键字)，这里 m/2≤k。
- 每个节点中的元素(关键字)从小到大排列。
- 每个元素(关键字)字左结点的值，都小于或等于该元素(关键字)。右结点的值都大于或等于该元素(关键字)。
B树查询流程
- 获取根节点的关键字进行比较，当前根节点关键字为M，E要小于M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
- 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
- 拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
B树的插入节点流程
定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;
遵循规则：
- 当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2） -1小于等于5-1（关键字数小于cei(5/2) -1就要进行节点合并，大于5-1就要进行节点拆分,非根节点关键字数>=2）；
- 满足节点本身比左边节点大，比右边节点小的排序规则;
B树节点的删除
- 当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1，小于等于5-1，非根节点关键字数大于2；
- 满足节点本身比左边节点大，比右边节点小的排序规则;
- 关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
5、B+ 树
B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构。
B+Tree 与 B-Tree 的结构很像，但是也有几个自己的特性：
- B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字大大增加；
- B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；
- B+树的根节点关键字数量和其子节点个数相等;
- B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样
特点：
在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定;
B-Tree 和 B+Tree 该如何选择呢？都有哪些优劣呢 ?
- B-Tree 因为非叶子结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而 B+Tree 所有的数据都在叶子结点，每次查找都得到叶子结点。所以在同样高度的 B-Tree 和 B+Tree 中，B-Tree 查找某个关键字的效率更高。
- 由于 B+Tree 所有的数据都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+Tree 只需要找到该关键字然后沿着链表遍历就可以了，而 B-Tree 还需要遍历该关键字结点的根结点去搜索。
- B+Tree 关键字的搜索采用的是左闭合区间，之所以采用左闭合区间是因为他要最好的去支持自增id，这也是mysql的设计初衷。即，如果id = 1命中，会继续往下查找，直到找到叶子节点中的1。
- 由于 B-Tree 的每个结点(这里的结点可以理解为一个数据页)都存储主键+实际数据，而 B+Tree 非叶子结点只存储关键字信息，而每个页的大小是有限的，所以同一页能存储的 B-Tree 的数据会比 B+Tree 存储的更少。
- 每个叶子节点都有一个指针，指向下一个数据，形成一个有序链表。
这样同样总量的数据，B-Tree 的深度会更大，增大查询时的磁盘 I/O 次数，进而影响查询效率。
举个实际应用栗子
如果上图中是用ID做的索引，如果是搜索X = 1的数据，搜索规则如下：
- 取出根磁盘块，加载1，28，66三个关键字。
- X <= 1 走P1，取出磁盘块，加载1，10，20三个关键字。
- X <= 1 走P1，取出磁盘块，加载1，8，9三个关键字。
- 已经到达叶子节点，命中1，接下来加载对应的数据，图中数据区中存储的是具体的数据。
6、B*树
B*树是B+树的变种，相对于B+树他们的不同之处如下：
- 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）
- B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
特点：
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；
