高性能MySql进化论:常见索引类型的原理及其特点的介绍
众所周知，索引对于
数据库性能的影响至关重要，但是索引为什么可以提高查询效率，以及索引的种类及其特点可能不是很清楚,本文将对常用的索引类型以及特点做一个简单的介绍
1 为什么要使用索引
首先来说一下索引为什么可以提高查询效率。普通查询的过程往往是通过整表的扫描来获得期望的结果，如果表的纪录非常的多，查询的效率肯定会很慢。而索引则会通过最大程度的降低扫描纪录的条数来提高效率，不同类型的索引往往会采取不同的策略来降低扫描的记录数，具体的策略将在后面进行描述。
首先看一个简单的例子，来说明索引的作用
在这个例子中使用了一张包含100,000条左右的字典表 ，比较是否包含索引的查询时间
[sql] mysql> select id,word, mean from dictionary where mean='DEFAULT2'; +--------+--------+----------+ | id | word | mean | +--------+--------+----------+ | 110003 |Random | DEFAULT2 | +--------+--------+----------+ 1 row inset (0.05sec) mysql> select id,word, mean from dictionary where word='Random'; +--------+--------+----------+ | id | word | mean | +--------+--------+----------+ | 110004 |Random | DEFAULR# | | 110003 |Random | DEFAULT2 | +--------+--------+----------+ 2 rows inset (0.00sec)
接下来看看为什么会时间上有所差别，通过执行计划可以看出，第一条语句执行了整表扫描，查询了110486条记录才得到想要的结果，而第二条语句使用了索引，只检索了2条记录就得到了想要的结果，这说明了索引的主要提速原理：查询的过程中减少扫描的记录数
[sql] mysql> explain select id,word, mean from dictionary wheremean='DEFAULT2'; +----+-------------+------------+-------+---------------+------+---------+------+--------+--------------------------+ | id |select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------+-------+---------------+------+---------+------+--------+--------------------------+ | 1 | SIMPLE | dictionary | All | NULL | word | 135 | NULL | 110486 | Using where; Usingindex | +----+-------------+------------+-------+---------------+------+---------+------+--------+--------------------------+ 1 row inset (0.00 sec) mysql>explain select id,word, mean from dictionary where word='Random'; +----+-------------+------------+------+---------------+------+---------+-------+------+--------------------------+ | id |select_type | table | type |possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------+------+---------------+------+---------+-------+------+--------------------------+ | 1 | SIMPLE | dictionary | ref | word | word | 102 | const | 2| Usingwhere; Using index | +----+-------------+------------+------+---------------+------+---------+-------+------+--------------------------+ 1 row inset (0.00 sec)
2 索引的类型
在大多数的RDBMS中，索引的特性由存储引擎决定，不同的存储引擎在索引的实现上可能会采用不同的实现,B-Tree Index以及Hash Index是比较常用的两种索引。这两种索引使用的底层数据结构是不同的，所以这两种索引在使用的过程中也有各自的特点
2.1 B-Tree Index
B-Tree索引是一种使用相对广泛的索引类型，在很多数据库中 (ORACLE,MYSQL) 也将它作为默认的索引类型，这种索引采用B-Tree数据结构来存储数据。
B-tree是以排序的方式存储数据并允许以O(log n)的运行时间进行查找，顺序读取，插入和删除的数据结构。概括来说是一个节点可以拥有多于2个子节点的二叉查找树。在B-Tree中，内部（非叶子）节点可以拥有，预先设定范围数量内的多个子节点。当数据被插入或从一个节点中移除，它的子节点数量发生变化。
下面是B-Tree的结构图
上图说明了B-Tree的工作原理，在根节点中定义了叶子节点值的区间范围，叶子中存储了实际的值。当进行查找时，首先会使用条件值在根节点中选择一个合适叶子节点区间，然后再用条件值和叶子层某个区间内的叶子节点的值进行比较。
举个例子来说明其原理，例如 学生表中的学生ID是有序递增的，图中的Key1 是100，Key2是200.当需要查询一个ID为90的学生时会在最左侧的叶子链表中进行搜索，如果需要查询一个ID为130的学生时，会在中间的叶子链表中进行查找。这样的查询方式因为避免了全表扫描，所以效率会大大的提高。
有一点需要注意，当把B-Tree索引建立在多个字段上时，（例如 建立索引时顺序为 LastName, FirstName,BrithDay）,则每个Key值都是LastName,FirstName,Brithday这样的数据结构,匹配的叶子节点值的过程是按照索引中