数据结构

二叉树到BST树的过滤

二叉树本身是无序的，有且仅有两个分支，查询某个数值时，需要挨个遍历查询。而我们遍历一个有序数组时可以使用二分查找的方法进行快速查询，这就过渡到了BST树：BST树全称为Binary Search Tree ，它的特点是插入数据的时候会调整节点的顺序， 左、根、右必须有序，左子树必须小于根节点，右子树必须大于根节点。如下：

BST树可以使用二分查找法进行查找，比如找6，则可以从根分开，直接从右侧去找，如下按红线顺序去找：

BST树到AVL树的过渡

但是BST树有个缺点，如果插入数据的顺序是递增或递减，则节点会无限延申，则就退化成链表，这又将时间复杂度回归到O(N)，为了解决这个问题，则在插入数据的时候尽量让树保持平衡，这就需要将节点进行左旋或右旋，这就变成了AVL树，即，平衡二叉树。如下图所示：

AVL平衡二叉树，最短子树和最长子树高度之差不能超过1，即在插入的时候必须要旋转，而旋转是需要浪费时间的，这说明AVL树通过插入性能的损失来弥补查询性能的提升

AVL树到红黑树的过渡

AVL树对于读系统来说，性能非常高，然而对于读写比例一致的系统，这种数据结构又会存在问题，这又演变出来了红黑树，红黑树的特点在于：最长子树只要不超过最短子树的两倍即可，让读写性能达到一个近似的平衡，下面我们可以用AVL树和红黑树的数据结构来对比一下，如下所示：

当插入6时，红黑树不再进行旋转

红黑树到B树的过渡

因为上面的树有且仅有两个节点，所以，随着数据的增多，树的深度会越来越深，这意味着IO次数越多，从而影响数据读取的效率。为了解决这个问题，则将有序二叉树转变成有序多叉树不就行了么？是的，可以这样存，那我们想没想过一个问题？这个节点到底怎么存？每一个节点能存多少条数据呢？我们看下面一张图，如果一个节点存3条记录，那么为了保证树的顺序，则存储的示意图如下所示：

上图中我们可以发现，每个节点存储的数据记录是个范围的数据，然而依然是有序的。此外还有一个特点，如果树的阶或树的度（degree）为2，则每个节点最多存1条记录，如果degree为3，则每个节点最多存2条记录，如果degree为4则每个节点最多存3条记录，以此类推。这个就是B树。
那么B树可以作为mysql索引的存储结构么？我们再来思考一个问题，实际的数据存储格式是什么样的呢？肯定是索引key、value就是数据行 这样的存储结构吧，下面看一个完整的3层B树存储数据的结构，如下图所示：

上图中：每个节点占用一个磁盘块，一个节点上有两个升序排序的的关键字和3个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分的3个范围域对应3个指针指向的子树的数据的范围域。
以根节点为例，key为16和34，p1指针指向的子树的数据范围为小于16，p2指针指向的子树的数据范围为16-34，p3指针指向的子树的数据范围为大于34。

如果想查找图中的28，则
1、首先根据根节点找到磁盘块1，读入内存，此时进行一次IO操作。
2、比较关键字28在区间范围16-34之间，则找到磁盘块1的指针p2。
3、根据p2找到磁盘块3，再进行比较，找到磁盘块3的指针p2，再根据p2找到磁盘块8的数据28.
此查找过程经历了3次io操作，我们知道，在innodb存储引擎中，每个节点的大小为16k，即第一层的数据范围为16k，第二层的数据范围也为16k，第三层的数据范围也为16k。因此可以得出结论，三层b树的可以存161616=4096条记录数。由于指针等占用了一部分空间，所以存储的数据一定是小于4096的。

B树过渡到B+树

现在再考虑一下，3层B树的结构可存放4096，那么如果随着数据量的增多，又需要添加更多的层数，这导致读取数据时又会增加的IO的操作。同时B树在每层节点上都存有数据，如果将非叶子节点只存储key 和指针，数据都存储到叶子节点上，那么这就过渡到了B+树。如下图所示：

上图中，也是3层的树，其在B树的基础上进行了如下优化
B+Tree的每个节点可以包含更多的节点，这样做的原因有两点，第一点：是为了降低树的高度，第二点是将数据范围变成多个区间，区间越多，数据检索越快。
非叶子节点存储key，叶子节点存储key和数据
叶子节点两两指针相互相连，符合磁盘的预读特性，顺序查询性能更高。