mysqlbtree索引概述

       B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型，这主要是因为B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现，值得注意的是mysql中innodb和myisam引擎中的B-tree索引使用的是B+tree（即每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历，并且除叶子节点外其他节点只存储键值和指针）。

   一般来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 B+tree的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个Leaf Node 上面出了存放索引键值和主键的相关信息之外，B+Tree还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。 

一：下面重点讲解下在mysql中innodb和myisam的b-tree索引的不同实现原理；

1）MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域仅仅存放的是指向数据记录的地址（也叫行指针），在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

2）InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

前面说过了，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据行记录的地址（行指针）。但是在innodb引擎中，btree索引分为两种，1，聚集索引（主键索引），2.二级索引，或者说叫辅助索引。InnoDB中的主键索引是聚集索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录（整行数据）。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主键索引。但是innodb的二级索引，保存的是索引列值以及指向主键的指针，所以我们使用覆盖索引的做优化处理就是针对mysql的innodb的索引而言的。

总结起来就是：

MyISAM引擎中leaf node存储的内容:

主键索引 ：仅仅存储行指针；

二级索引：存储的也仅仅是行指针；

InnoDB引擎中leaf node存储的内容

主键索引 ：聚集索引存储完整的数据（整行数据）

二级索引：存储索引列值+主键信息

下面这张图显示mysql中innodb和myisam引擎的索引实现的原理

二：接下来说下通过btree索引检索数据的过程：

myisam和innodb引擎都是使用B+tree实现btree索引，检索数据的过程中，从根节点到子节点，然后找到叶子节点，接着找到叶子节点中存储的data的过程是一样的，只不过因为myisam和innodb引擎中的叶子节点中的data中存储的内容是不一样的（前文介绍了），所以找到叶子节点中的data之后再找真正数据的过程是不一样的，然后根据前文介绍的不同存储引擎中叶子节点data中存储的不同数据，例如innodb中的主键索引叶子节点存储的是完整数据行，所以根据innodb中的主键索引遍历数据时，找到了叶子节点的data，就可以找到数据，至于myisam中叶子节点data存储的是行指针，也就是找到叶子节点的data后，再根据行指针去找到真正的数据行。

下面重点去说由根节点找叶子节点中的data域的过程：

为了对比，可以先看下B-tree实现原理：

B+tree实现原理如下图：

通过两张图可以看出来，相对于B-tree来说，B+Tree根节点和子节点只保存了键值和指针，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度，并且B+Tree中的叶子节点比B-tree多存储了指向下一个叶子节点的指针，这样更方便叶子节点的范围遍历。

每个节点占用一个磁盘块的磁盘空间，一个节点上有n个升序排序的关键字和（n+1)个指向子树根节点的指针，这个指针存储的是子节点所在磁盘块的地址（注意这里的n是创建索引的时候，根据数据量计算出来的，如果数据量太大了，三层的可能就满足不了，就需要四层的B+tree，或者更多层）,然后n个关键字划分成（n+1)个范围域，然后每个范围域对应一个指针，来指向子节点，子节点又从新根据关键字再次划分，然后指针指向叶子节点。

针对下图具体解释下B+tree索引的实现原理（修改自网络）：

针对上图，每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

然后针对上图模拟下 where id=29的具体过程：（首先mysql读取数据是以块（page）为单位的）。

首先根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

比较关键字29在区间（17,35），找到磁盘块1的指针P2。

根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】

比较关键字29在区间（26,30），找到磁盘块3的指针P2。

根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】

在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

相对于B-tree来说，B+Tree根节点和子节点只保存了键值和指针，

查看mysql中的页的大小：

MySQL [meminfo]> show variables like 'innodb_page_size';

+------------------+-------+

| Variable_name | Value |

+------------------+-------+

| innodb_page_size | 16384 |

+------------------+-------+

1 row in set (0.00 sec)

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

三：下面说下mysql中innodb引擎中聚簇表和myisam中非聚簇表的遍历数据的不同

如下图（来自网络）：

看上去聚簇索引的效率明显要低于非聚簇索引，因为每次使用辅助索引检索都要经过两次B+树查找，这不是多此一举吗？聚簇索引的优势在哪？

1 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。

2 辅助索引使用主键作为"指针" 而不是使用行地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个"指针"，使用聚簇索引可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。

四：最后说下mysql中的B+tree索引的好处和限制（摘自高性能mysql第三版）

（一）可以使用的情况：

可以使用btree索引的查询类型，btree索引使用用于全键值、键值范围、或者键前缀查找，其中键前缀查找只适合用于根据最左前缀的查找。前面示例中创建的多列索引对如下类型的查询有效：

1）全值匹配

全值匹配指的是和索引中的所有列进行匹配，即可用于查找姓名和出生日期

2）匹配最左前缀

如：只查找姓，即只使用索引的第一列

3）匹配列前缀

也可以只匹配某一列值的开头部分，如：匹配以J开头的姓的人（like 'J%')，这里也只是使用了索引的第一列，且是第一列的一部分

4）匹配范围值

如查找姓在allen和barrymore之间的人，这里也只使用了索引的第一列

5）精确匹配某一列并范围匹配另外一列

如查找所有姓为allen，并且名字字母是K开头的，即，第一列last_name精确匹配，第二列first_name范围匹配

6）只访问索引的查询

btree通常可以支持只访问索引的查询，即查询只需要访问索引，而无需访问数据行，即，这个就是覆盖索引的概念。需要访问的数据直接从索引中取得，这个是针对innodb中btree索引而言的。

因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的order by操作，一般来说，如果btree可以按照某种方式查找的值，那么也可以按照这种方式用于排序，所以，如果order by子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。

 (二）下面是关于btree索引的限制：

1）如果不是按照索引的最左列开始查找的，则无法使用索引(注意，这里不是指的where条件的顺序，即where条件中，不管条件顺序如何，只要where中出现的列在多列索引中能够从最左开始连贯起来就能使用到多列索引)

2）不能跳过索引中的列，如创建了多列索引（姓，名，出生日期）：查询条件为姓和出生日期，跳过了名字列，这样，多列索引就只能使用到姓这一列。

3）如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询，如：where last_name=xxx and first_name like ‘xxx%’ and dob=’xxx’;这样，first_name列可以使用索引，这列之后的dob列无法使用索引。

总结：mysql中常用的引擎有innodb和myisam,这两个引擎中创建的默认索引都是B-tree索引，而都是B+tree结构实现的，并且innodb和myisam具体叶子节点存储的内容有所不同，然后覆盖索引是针对innodb引擎的索引而言的，因为myisam引擎中b-tree索引的叶子节点存储的仅仅是行指针。