二叉树、B-Tree、B+Tree、红黑树、平衡二叉树（AVL Trees）
平衡二叉树 (AVL Trees)
平衡二叉树是一种特殊的二叉树-所以他也满足前面说到的二叉树的两个特性-同时还有一个特性：
它的左右两个子树的高度差的绝对值不超过1-并且左右两个子树都是一棵平衡二叉树。
大家也看到了前面[35 27 48 12 29 38 55]插入完成后的图-其实就已经是一颗平衡二叉树。
那如果按照[12 27 29 35 38 48 55]的顺序插入一颗平衡二叉树-会怎么样呢？我们看看插入以及平衡的过程：
!这棵树始终满足平衡二叉树的几个特性而保持平衡！这样我们的树也不会退化为线性链表了！我们需要查找一个数的时候就能沿着树根一直往下找-这样的查找效率和二分法查找是一样的呢！
一颗平衡二叉树能容纳多少的结点呢？这跟树的高度是有关系的-假设树的高度为h-那每一层最多容纳的结点数量为2^(n-1)-整棵树最多容纳节点数为2^0+2^1+2^2+…+2^(h-1)。这样计算-100w数据树的高度大概在20左右-那也就是说从有着100w条数据的平衡二叉树中找一个数据-最坏的情况下需要20次查找。如果是内存操作-效率也是很高的！但是我们数据库中的数据基本都是放在磁盘中的-每读取一个二叉树的结点就是一次磁盘IO-这样我们找一条数据如果要经过20次磁盘的IO？那性能就成了一个很大的问题了！那我们是不是可以把这棵树压缩一下-让每一层能够容纳更多的节点呢？虽然我矮-但是我胖啊…
B-Tree
这颗矮胖的树就是B-Tree-注意中间是杠精的杠而不是减-所以也不要读成B减Tree了~
那B-Tree有哪些特性呢？一棵m阶的B-Tree有如下特性：
> 1、每个结点最多m个子结点。
> 2、除了根结点和叶子结点外-每个结点最少有m/2（向上取整）个子结点。
> 3、如果根结点不是叶子结点-那根结点至少包含两个子结点。
> 4、所有的叶子结点都位于同一层。
> 5、每个结点都包含k个元素（关键字）-这里m/2≤k
是不是感觉跟丈母娘张口问你要彩礼一样-列一堆的条件-而且每一条都让你很懵逼！下面我们以一个[0,1,2,3,4,5,6,7]的数组插入一颗3阶的B-Tree为例-将所有的条件都串起来-你就明白了！
!img !img !img !img !img !img !img
那么-你是否对B-Tree的几点特性都清晰了呢？在二叉树中-每个结点只有一个元素。但是在B-Tree中-每个结点都可能包含多个元素-并且非叶子结点在元素的左右都有指向子结点的指针。
如果需要查找一个元素-那流程是怎么样的呢？我们看下图-如果我们要在下面的B-Tree中找到关键字24-那流程如下 !img !img !img !img
从这个流程我们能看出-B-Tree的查询效率好像也并不比平衡二叉树高。但是查询所经过的结点数量要少很多-也就意味着要少很多次的磁盘IO-这对 性能的提升是很大的。
前面对B-Tree操作的图我们能看出来-元素就是类似1、2、3这样的数值-但是数据库的数据都是一条条的数据-如果某个数据库以B-Tree的数据结构存储数据-那数据怎么存放的呢？我们看下一张图
!img
普通的B-Tree的结点中-元素就是一个个的数字。但是上图中-我们把元素部分拆分成了key-data的形式-key就是数据的主键-data就是具体的数据。这样我们在找一条数的时候-就沿着根结点往下找就ok了-效率是比较高的。
B+Tree
B+Tree是在B-Tree基础上的一种优化-使其更适合实现外存储索引结构。B+Tree与B-Tree的结构很像-但是也有几个自己的特性：
> 1、所有的非叶子节点只存储关键字信息。 > 2、所有卫星数据（具体数据）都存在叶子结点中。 > 3、所有的叶子结点中包含了全部元素的信息。 > 4、所有叶子节点之间都有一个链指针。
如果上面B-Tree的图变成B+Tree-那应该如下： !img
大家仔细对比于B-Tree的图能发现什么不同？ 1、非叶子结点上已经只有key信息了-满足上面第1点特性！ 2、所有叶子结点下面都有一个data区域-满足上面第2点特性！ 3、非叶子结点的数据在叶子结点上都能找到-如根结点的元素4、8在最底层的叶子结点上也能找到-满足上面第3点特性！ 4、注意图中叶子结点之间的箭头-满足满足上面第4点特性！
B-Tree or B+Tree？
在讲这两种数据结构在数据库中的选择之前-我们还需要了解的一个知识点是操作系统从磁盘读取数据到内存是以磁盘块（block）为基本单位的-位于同一个磁盘块中的数据会被一次性读取出来-而不是需要什么取什么。即使只需要一个字节-磁盘也会从这个位置开始-顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理： 当一个数据被用到时-其附近的数据也通常会马上被使用。 预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块-硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块-每个存储块称为一页（在许多操作系统中-页得大小通常为4k）。
B-Tree和B+Tree该如何选择呢？都有哪些优劣呢？ 1、B-Tree因为非叶子结点也保存具体数据-所以在查找某个关键字的时候找到即可返回。而B+Tree所有的数据都在叶子结点-每次查找都得到叶子结点。所以在同样高度的B-Tree和B+Tree中-B-Tree查找某个关键字的效率更高。 2、由于B+Tree所有的数据都在叶子结点-并且结点之间有指针连接-在找大于某个关键字或者小于某个关键字的数据的时候-B+Tree只需要找到该关键字然后沿着链表遍历就可以了-而B-Tree还需要遍历该关键字结点的根结点去搜索。 3、由于B-Tree的每个结点（这里的结点可以理解为一个数据页）都存储主键+实际数据-而B+Tree非叶子结点只存储关键字信息-而每个页的大小有限是有限的-所以同一页能存储的B-Tree的数据会比B+Tree存储的更少。这样同样总量的数据-B-Tree的深度会更大-增大查询时的磁盘I/O次数-进而影响查询效率。 鉴于以上的比较-所以在常用的关系型数据库中-都是选择B+Tree的数据结构来存储数据！下面我们以mysql的innodb存储引擎为例讲解-其他类似sqlserver、oracle的原理类似！
#### innodb引擎数据存储
在InnoDB存储引擎中-也有页的概念-默认每个页的大小为16K-也就是每次读取数据时都是读取4*4k的大小！假设我们现在有一个用户表-我们往里面写数据
!img
这里需要注意的一点是-在某个页内插入新行时-为了不减少数据的移动-通常是插入到当前行的后面或者是已删除行留下来的空间-所以在某一个页内的数据并不是完全有序的（后面页结构部分有细讲）-但是为了为了数据访问顺序性-在每个记录中都有一个指向下一条记录的指针-以此构成了一条单向有序链表-不过在这里为了方便演示我是按顺序排列的！
由于数据还比较少-一个页就能容下-所以只有一个根结点-主键和数据也都
