今天研究下，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多存储了指向下一个叶子节点的指针，这样更方便叶子节点的范围遍历。