理解数据库索引

首先通过一个非常简单的例子来解释为什么你需要数据库索引。

假设我们有一张数据表Emplyee，该表有三列：

Employee_Name,Employee_Age,Employee_Address

表中有几万条记录。现在，我们要执行下面这条查询语句，查找出所有名字叫“Jesus”的员工的详细信息：

SELECT * FROM Employee

WHERE Employee_Name = 'Jesus'

没有索引会发生什么？

当我们执行上面这条查询后，数据库中究竟发生了什么？数据库系统会逐行的遍历整张表，对于每一行都要检查其Employee_Name字段是否等于“Jesus”。因为我们要查找所有名字为“Jesus”的员工，所以当我们发现了一条名字是“Jesus”的记录后，并不能停止继续查找，因为可能有其他员工也叫“Jesus”。这就意味着，对于表中的几万条记录，数据库每一条都要检查。这就是所谓的“全表扫描”（ full table scan）。

数据库索引是怎么提高查询效率的？

也许你在抱怨，这么简单的事情还要做全表扫描，这简直就是用人眼检查整个表，效率太低了！数据库就不能更聪明点吗？也许你已经根据文章标题猜到了，在这里使用索引会大有帮助。索引的最大作用就是加快查询速度，它能从根本上减少需要扫表的记录/行的数量。

一句话理解什么是索引！

索引就是数据结构！

进一步说该数据结构中存储了这张表中某一列的所有值，就是说索引是基于数据表中的某一列创建的。再啰嗦一遍：一个索引是由表中某一列上的数据组成，并且这些数据存储在某个数据结构中。最后一遍：索引就是数据结构。嗯，记住这句话吧！

索引使用哪种数据结构？

B- 树是用于索引最常见的数据结构。这是因为B-树有较好的时间效率，在查找、删除、插入操作上其时间复杂度都是对数阶，即O(logn)。另外一个重要原因是，存储在B-树上的数据是有序的。通常，创建索引时使用哪种数据结构是由数据库决定的。但是，有些数据库，你可以指定使用哪种数据结构创建索引。

Hash索引怎么工作的？

Hash表是另外一种可以被用作索引的数据结构，这种索引称作hash索引。Hash表的查询效率是非常高的，尤其对比较字符串相等的查询，如果使用了hash索引，那么查询速度是极快的。例如，前面讨论过的查询语句(SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’),如果在Employee_Name列上创建hash索引，会显著提高该查询的效率。Hash索引的原理是，将列值作为hash表的key,而value中保存行的指针。Hash表就是一个关联数组(associative array，关联数组又称映射Map或字典Dictionary)，典型的结构看起来是这个样子：

Jesus -> 0x28939

0x28939指向“Jesus”这一行在内存中的地址（Mysql 只有memory引擎支持Hash索引）。使用hash索引直接通过"Jesus"获取这一行在内存中的地址指针，明显比通过全表扫描查找出Employee_Name=’Jesus‘的行要快的多。

Hash索引的缺点！

Hash表是无序的数据结构，在很多情况下，使用hash索引并不能提高效率。例如，你想查找出所有年龄小于40的员工，就不能使用hash索引。因为Hash索引只适用于键值对查询，即等值查询(例如"WHERE name=`Jesus`)，不能用于范围查询。Hash表中的键值映射隐含的告诉了你，hash表中的键并没有按照特定的顺序排序。而且hash表不如B- 树灵活，所以数据库系统通常会选择B-树作为索引的默认数据结构而不是hash表。

还有其他类型的索引吗？

R- 树索引通常用来解决空间问题。例如，你要查找“距离我2km以内的星巴克”，类似这种查询使用R-树索引会有很好的性能提升。空间数据库代表有PostGIS，MySQL Spatial。

还有一种位图(bitmap)索引，位图索引一般用在布尔类型的列上。这些列都具有低选择性(low selectivity)的特点。因为布尔类型的列只有1和0(True和False)两种值，假设这张表有10000条记录，该列的选择性为2/10000 ×100%=0.02%,这么低的选择性很适合很使用位图索引。更多关于索引的选择性问题，大力戳《不知道"选择性"怎么能说懂索引呢》。

索引是怎么提高查询效率的？

索引的本质上是一个存储列值的数据结构。如果在某列上使用了B-树索引，那么这些列值在索引中是被排过序的，有序的值是索引能提高查询性能的主要原因。

当我们在Employee_Name列上创建了B-树索引后，再去执行前面提到的SQL语句时，数据库就不用再对Emplyee表做全表扫描了，而是直接从索引中查找名字叫“Jesus”的员工。由于B-树索引会把所有员工的名字按字母表顺序进行排序，这样以'J'开始的名字都会相邻，查找起来就会很快。值得注意的是，索引除了保存员工姓名还会保存该员工在数据表中所在行的指针，这样就可以检索到行中其他列的数据，以获取员工更多的信息。

索引中保存了什么？

现在你知道了索引是创建在表中的某列上，索引中保存了该列的所有数据。这里要理解的是，索引并不保存其他列的数据。例如我们在Employee_Name列上创建了索引，同一张表的Employee_Age 、Employee_Address列的数据不会被保存到索引中。如果我们在索引中保存了其他列的数据，那无异于对整张表做copy，浪费空间不说效率还低，这是非常愚蠢的做法。

索引中保存了行的指针

那么，问题来了？当我们在索引中查找到“Jesus”后，怎么获取这一行中的其他列值（比如Jesus的年龄和地址）。其实很简单，因为索引中保存了关联行在表中的位置的指针。也就是说，索引除了保存列值之外，还保存了与该列值关联的行在表中的位置信息。因此，Employee_Name索引中的值(或节点)看起来大概是这个样子 (“Jesus”, 0x82829)，0x82829就是“Jesus”这一行在磁盘上的存储地址(指针)。如果没有这个指针，只有一个单独的列值，对我们是没意义的，因为我们无法获取这一行的其他信息。

数据库怎么知道什么时候使用索引？

当我们执行这样一条查询时

SELECT * FROM Employee
WHERE Employee_Name = ‘Jesus’

数据库首先会检查Employ_Name列上有没有创建索引。如果Employee_Name列上有索引，数据库还要判断是否应该使用索引检索要查找的值，因为有些情况，做全表扫描要比使用数据库索引高效。有些情况是什么情况呢？大力戳《全表扫描！你的数据库有点弱智》

可以强制让数据库使用索引查询吗？

通常，你不需要告诉数据库什么时候使用索引，这由数据库自己决定。但是，对于大多数数据库（例如Oracle和Mysql），你可以强制让数据库使用索引，例如Mysql可以通过“force index”来强制使用索引。

怎么创建索引？

这里我们为本文中一直提到的Emloyee_Name列创建索引：

CREATE INDEX name_index

ON Employee (Employee_Name)

怎么创建联合索引？

我们也可以基于Employee表的两列创建索引：

CREATE INDEX name_index

ON Employee (Employee_Name, Employee_Age)

对于数据库索引有没有好的类比？

图片：书籍《更喜欢摄影》的目录页

这里有个很经典的类比，把数据库索引想象成一本书的目录。假设你有一本介绍狗的书，现在你要看关于哈士奇的章节。你会去浏览整本书吗？这相当于数据库的全表扫描，浪费时间啊。然而你可以直接查看这本书的目录，它会告诉你关于哈士奇的章节在第几页。就像书的目录中包含页码，类似的，数据库的索引包含指针，指向你用SQL语句正在查找的那一行。

使用索引有什么代价？

那么，创建数据库索引有什么缺点？首先，占用空间。你的表越大，索引需要的空间就越大。另外会影响数据库性能，你对数据表进行增删改操作，同样的操作还要在索引上执行一次。

请记住，索引中始终维护着和被索引列相同的数据。

基本原则

只在频繁查询的列上创建索引！

英文原文：http://www.programmerinterview.com/index.php/database-sql/what-is-an-index/

相关阅读：

    《不知道"选择性"怎么能说懂索引呢》    

    《全表扫描！你的数据库有点弱智》