数据结构其实分2大部分：
存储结构：数据根据什么规则存储，比如索引存储的时候要根据树的规则去存储。
逻辑结构：数据本身的结构，比如索引内部其实是一个复合结构，内部除了自己指向的数据地址还有其他节点相关地址。
起初根据查找效率的需求，设计人员选择了单独开辟扇区用来存放索引，就好像字典的索引一个道理。
存储结构和逻辑结构结合起来就帮助我们查找数据的时候可以尽量减少查找次数（底层就是扇区的读取次数）
二叉树的结构也可以帮我们形象理解索引的查找次数与普通链表的差别，同样的数据，普通链表最糟糕情况要查遍所有数据节点，而二叉树最多的查询次数跟树的层数有关，明显比链表要少。
平衡二叉树是在二叉树基础上的进一步优化，用“平衡”形象的表述了怎样优化二叉树的结构，从而优化查询效率。简单说就是父节点要求2边子节点层级要尽量一样，最大高度差为1。
平衡二叉树的结构概念上很好，但是有个问题，索引结构的改变导致磁盘上的索引数据也需要频繁读写调整扇区，这也导致了性能问题。
针对以上问题，设计人员又做了调整：
首先取消单独开辟单独block存放索引，让数据block节点本身就带索引信息，数据block节点本身就是索引节点。
每个block内存储的数据还是顺序排列，能排多少个跟数据本身占用的空间有关。
一个节点能延伸多少个引用关系跟内部的数据有关，而不是二叉树那样的顶多2条线路，大致就是2个端点会各自延伸出一条线路，block内部数据之间如果还能再插入数据，那随着新block的申请，就会延伸出一个新的线路指向新的block。
block内的数据并不是插入就不会再移动的，而是随着block被填满，再插入数据的时候会先发生分裂（block内数+新填入数据序列均分）成2个block（新申请一块，再平分填入2个block），然后选一个靠中间的数据（通常是较大的那个）升级到父节点（这里又是一个block读写），并且调整引用线路，如果父节点也填满了，则在这一层也发生分裂并且有一个数据提升到上一级父节点。
以上结构就是btree（多路查找树）。
btree操作的特点：
1）每次分裂都会使block留有一些空隙供下一次插入。
2）与二叉树不同，btree的延伸是从下到上的。
btree优点：
1）每次调整都是局部的block读写，相比二叉树效率要好一些。
2）相比二叉树，btree的层级要更少，查询效率要更高（block读取次数）
btree的缺陷：
因为btree的节点内存放的是数据，因此实际每个block能分出的线路是有限的。因此，设计人员又提出了b+tree。
b+tree：
b+tree的遍历和分裂逻辑与btree一样，最大的变化有2点：
1）叶子节点只是数据，非叶子节点只存放索引，索引点只保留数据的引用即可。这样放大了索引查找的效率，又不会像二叉树那样多的读写block。查找流程上，b+tree相当于在btree基础上，多了一次查找索引指向的数据所在block。
2）叶子节点的数据是一个顺序排列的链表，这样可以方便按范围查找。
网友评论