MySQL中B+Tree索引原理

234cfds1

　　来源：http://blog.csdn.net/u013235478/article/details/50625677
　　B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。
二叉查找树
　　二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。
　　如下图所示就是一棵二叉查找树，

http://img.blog.csdn.net/20160202203355523

　　对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次
　　二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：

http://img.blog.csdn.net/20160202203448944

　　但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。
平衡二叉树（AVL Tree）
　　平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差 show variables like 'innodb_page_size';11　　而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。
　　B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。
　　一棵m阶的B-Tree有如下特性：
　　1. 每个节点最多有m个孩子。
　　2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
　　3. 若根节点不是叶子节点，则至少有2个孩子
　　4. 所有叶子节点都在同一层，且不包含其它关键字信息
　　5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
　　6. 关键字的个数n满足：ceil(m/2)-1