一句话理解数据库索引 - 忙碌的键盘

/ 技术 / 无站内评论 / 483浏览




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


假设我们有一张数据表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)


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



</en-media>


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


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


使用索引有什么代价?


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


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


基本原则


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


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


相关阅读:


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


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


 




召唤蕾姆
琼ICP备18000156号

鄂公网安备 42011502000211号