今天研究下，mysql中的B-tree索引，通过这篇文章你可以了解到，mysql中的btree索引的原理，检索数据的过程，innodb和myisam引擎中btree索引的不同，以及btree索引的好处和限制。

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)