众所周知，索引对于数据库性能的影响至关重要，但是索引为什么可以提高查询效率，以及索引的种类及其特点可能不是很清楚,本文将对常用的索引类型以及特点做一个简单的介绍

1        为什么要使用索引

首先来说一下索引为什么可以提高查询效率。普通查询的过程往往是通过整表的扫描来获得期望的结果，如果表的纪录非常的多，查询的效率肯定会很慢。而索引则会通过最大程度的降低扫描纪录的条数来提高效率，不同类型的索引往往会采取不同的策略来降低扫描的记录数，具体的策略将在后面进行描述。

首先看一个简单的例子，来说明索引的作用

在这个例子中使用了一张包含100,000条左右的字典表 ，比较是否包含索引的查询时间

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条记录就得到了想要的结果，这说明了索引的主要提速原理：查询的过程中减少扫描的记录数

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的结构图