「MySQL高级篇」MySQL索引原理，设计原则( 三 ) _生活百科

只需遍历叶子节点，就可以实现整棵树的遍历。

?
MySQL中的B+TreeMySql索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针(整体类似一个双向链表的结构)，就形成了带有顺序指针的B+Tree，提高区间访问的性能。?
细心的同学可以看出，这张图跟我们的二叉查找树简图的一个最大区别是什么？

从二叉查找树过渡到B树，有一个显著的变化就是，一个节点可以存储多个数据了，相当于一个磁盘块里边可以存储多个数据，大大减少了我们的 IO次数！！

MySQL中的 B+Tree 索引结构示意图：

文章插图
二叉查找树简图：

文章插图
索引原理BTree索引：

文章插图
初始化介绍浅蓝色的称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示)如磁盘块1包含数据项17和35，包含指针P1、P2、P3,P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。

真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99 。`
非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。`

查找过程如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO 。在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中通过二分查找搜索到29，结束查询，总计三次IO 。真实的情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。
索引分类在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。?
每一个索引在InnoDB里面对应一棵B+树。假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引。这个表的建表语句是：
mysql> create table T(id int primary key,k int not null,name varchar(16),index (k))engine=InnoDB;表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下：

文章插图
从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引数据表的主键列使用的就是主键索引，且会默认创建，这也是为什么，我们还没学索引的时候，老师经常跟我们说根据主键查会快一点，原来主键本身就建好了索引。主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。
辅助索引辅助索引的叶子节点内容是主键的值。在InnoDB里，辅助索引也被称为二级索引（secondary index）。?
如下图：