一、基础概念
1、定义
索引（Index）是帮助MySQL高效获取数据的数据结构
2、存储引擎
mysql有不同的存储引擎，如MyISAM、InnoDB，不同存储引擎，对索引的实现是不一样的。
二、MyISAM
MyISAM引擎使用B+Tree作为索引结构。
主索引和辅助索引叶节点的data域都存放的是数据记录的地址。
图1是MyISAM索引的原理图，这里设表一共有三列，假设我们以Col1为主键，图1是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件叶节点的data域仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分，看完文章你会理解这句话的含义。
图1
三、InnoDB
InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
从上文知道，MyISAM索引文件叶节点data域仅保存数据记录的地址。而在InnoDB中，主索引的叶节点data域保存了完整的数据记录。如果这个索引的key是数据表的主键，则InnoDB表数据文件本身就是主索引。图2是InnoDB主索引的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域，见图3。
图2
图3
四、b-tree与b+tree区别
以InnoDB存储引擎为例。
b+tree：
1、内节点只存储key和指针，不存储data，见图2图3。
2、如果是主索引，叶节点data域保存了完整的数据记录，见图2。如果是辅助索引，叶子节点的data域存放的是主键，见图3。
3、增加了顺序访问指针。在每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能。例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
图4
b-tree：
1、b-tree的内节点和叶节点data域都保存了除key外完整的数据记录。
图5
END
如有错漏，望指出。
网友评论