MySQL索引原理——B树

1、MyISAM是MySQL 5.5之前版本默认的存储引擎，从5.5之后，InnoDB开始成为MySQL默认的存储引擎。MyISAM和InnoDB都是使用B+树实现主键索引、唯一索引和非主键索引。

2、InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。

3、B-Tree定义一：

一棵m阶的B-Tree,或者为空树，或者满足下列特性： 

• 树中每个结点至多有m棵子树； 
• 若根结点不是叶子结点，则至少有两棵子树； 
• 除根节点之外的所有非终端结点至少有[m/2]棵子树； 
• 所有非终端结点中包含下列信息数据: (n,A0,K1,A1,K2,A2……Kn,An) 。其中，n为关键字的数目，K(i)为关键字，且K(i) < K(i+1), Ai为指向子树根结点的指针，且指针A(i-1)所指子树中所有结点的关键字均小于Ki，Ai所指子树中所有结点的关键字均大于Ki； 
• 所有叶子结点都出现在同一层次上；

B-Tree定义二：

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。
• h为一个正整数，称为B-Tree的高度。
• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
• 子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null。
• 所有叶节点具有相同的深度，等于树高h。
• key和指针互相间隔，节点两端是指针。
• 一个节点中的key从左到右递增排列。
• 如果某个指针在节点node的左右相邻key分别是key1和key2且不为null，则其指向的节点的所有key小于key2且大于key1.

4、B+Tree

与B-Tree相比，B+Tree有以下不同点：

• 每个节点的指针上限为2d而不是2d+1。
• 内节点不存储data，只存储key；叶子节点不存储指针。
• 非叶子结点的子树指针与关键字个数相同；
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-Tree左右都是开区间）；
• 为所有叶子结点增加一个链指针；

5、数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。

上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是只存储相应行数据的辅助索引值和聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

6、InnoDB索引实现：

InnoDB采用B+tree作为索引结构，但具体实现方式却与MyISAM不同。

1）主键索引：

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

(图inndb主键索引）是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2）InnoDB辅助索引

InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义很多索引，则争取尽量把主键定义得小一些，因为InnoDB 不会压缩索引。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁地分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

 InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

3）InnoDB辅助索引与null

值为NULL的二级索引记录被放在了B+树的最左边，这是因为设计InnoDB的大叔有这样的规定：

We define the SQL null to be the smallest possible value of a field.

也就是说他们把SQL中的NULL值认为是列中最小的值。

7、B树（B-树/B+树）插入操作：

插入一个元素时，首先查看在B树中是否存在，如果不存在，即查找操作会在叶子结点处结束，然后在叶子结点中插入该新的元素，注意：如果叶子结点空间足够，则需要向右移动该叶子结点中大于新插入关键字的元素（以保证节点的顺序性），如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。如下图所示：

8、B树（B-树/B+树）删除操作

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中；如果没有，则直接删除。删除元素，移动相应元素之后（如果没孩子节点则没有移动），如果某结点中元素数目（即关键字数）小于ceil(m/2)-1，则需要看其某相邻兄弟结点是否丰满（结点中元素个数大于ceil(m/2)-1），如果丰满，则向父节点借一个元素来满足条件；如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。

9、B*-tree

B*-tree是B+-tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。给出了一个简单实例，如下图所示：

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂：当 如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

10、总结：

通过以上介绍，大致将B树，B+树，B*树总结如下：

B树：有序数组+平衡多叉树；

B+树：有序数组链表+平衡多叉树；

B*树：一棵丰满的B+树。

相比B-tree，B+tree有个好处，那就是方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

当然，B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。

有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。

mysql 底层存储是用B+树实现的，因为MySQL的索引是存储在磁盘上的。内存中B+树是没有优势的，但是一到磁盘，B+树的威力就出来了。

11、相关参考文档：

http://blog.csdn.net/ifollowrivers/article/details/73614549 MySQL中B+Tree索引原理

http://blog.csdn.net/define_danmu_primer/article/details/70757784 MySQL索引使用的数据结构：B-Tree和B+Tree

http://blog.csdn.net/u013400245/article/details/52824744 B树B+树的原理和操作

https://www.cnblogs.com/gym333/p/6877023.html 【数据结构】B-Tree, B+Tree, B*树介绍 转

http://blog.csdn.net/endlu/article/details/51720299 BTree和B+Tree详解

http://blog.csdn.net/u013400245/article/details/52824744 B树B+树的原理和操作

https://www.jianshu.com/p/17a7b3d321d8 B-树和B+树

https://mp.weixin.qq.com/s/CEJFsDBizdl0SvugGX7UmQ MySQL中IS NULL、IS NOT NULL、!=不能用索引？胡扯！

https://mp.weixin.qq.com/s/-r3qsTMwp8jGLxyVEmtDcg  MySQL中MyISAM与InnoDB区别及选择

https://www.cnblogs.com/xiaoxi/p/6868087.html  MySQL和B树的那些事