面试官爱的数据库索引连环问~

2021-11-18 00:00:00 索引 查询 数据 数据库 数据结构

以下文章来源于爱笑的架构师 ,作者雷小帅  

前段时间一直在面试,问了很多候选人数据库索引相关的知识,能答好的不是很多,令人惋惜啊,我也想留你啊……

面试官:了解过数据库索引吗?

候选人:听过一些,底层数据结构好像是二叉树,不对,好像是 B 树,哦,我想起来了,好像是 B+树……(像极了当年面试的我)

面试官:听过哈希索引吗?

候选人:我知道哈希表,哈希索引没听过

面试官:今天面试先到这里了,回去等消息吧……

温馨提示:本文是数据库索引的入门篇

先引入一个简单的示例,通过示例操作解释一下为什么需要数据库索引。

假设我们有一个名为 t_employee 的数据库表,这个数据库表有三列:name,age,address,数据量有上万行。

如果我们想要查找所有名为「leixiaoshuai」员工的详细信息,只需要写一个简单的 SQL 语句就可以搞定,相信大家都会写。

SELECT * FROM t_employee 
WHERE name = 'leixiaoshuai'

如果没有索引,会发生什么?

一旦我们运行了这条 SQL 查询语句,在数据库内部是如何工作的呢?数据库会搜索 t_employee 表中的每一行,从而确定员工的名字(name)是否为 ‘leixiaoshuai’。由于我们想要得到每一个名字为 leixiaoshuai 的雇员信息,在查询到个符合条件的行记录后,不能停止查询,因为可能还有其他符合条件的行。所以,必须一行一行的查找直到后一行,这就意味数据库不得不检查上万行数据才能找到所有名字为 leixiaoshuai 的员工。这就是所谓的全表扫描

数据库索引如何帮助提高性能?

你可能会想:「这么简单的查询语句居然还需要全表扫描,数据库也太笨了吧?!」

这就类似于用人眼从头到尾逐字逐句读一本书,效率太低了!

那应该怎么办?聪明的你肯定想到解决方案了:「加个索引啊」。

这就是索引派上用场的时候了,使用索引的目的就是**通过减少表中需要检查的记录/行的数量来加速搜索查询。**说的再简单点:「索引就是用来加速查询的」。

什么是索引?

那么问题来了,什么是索引呢?索引本质是一种数据结构(常见的是 B+树),是在表的列上创建的。

索引的数据结构是什么样的?

常见MySQL索引一般分为:Hash索引和**B+**树索引,InnoDB引擎中默认的是B+树。

B+树 是常用于索引的数据结构,时间复杂度低:查找、删除、插入操作都可以可以在 logn 时间内完成。另外一个重要原因存储在 B+树 中的数据是有序的

在B+树常规检索场景下,从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动,而且基于索引的顺序扫描时,也可以利用双向指针快速左右移动,效率非常高。

哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。

哈希表索引是如何工作的?

如果你在创建索引时指定数据结构为「哈希表」,那这些索引也可称为「哈希索引」。

哈希索引的优点非常明显,在一定场景下,检索指定值时哈希表的效率极高。比如上面我们讨论的一个查询语句:SELECT * FROM t_employee WHERE name = ‘leixiaoshuai’,如果在 name 列上加一个哈希索引,检索速度有可能会成倍提升。

哈系索引的工作方式是将列的值作为索引的键值(key),键值相对应实际的值(value)是指向该表中相应行的指针。因为哈希表基本上可以看作是关联数组,一个典型的数据项就像 「leixiaoshuai => 0x996996」,而 0x996996 是对内存中表中包含 leixiaoshuai 这一行的引用。在哈系索引的中查询一个像 leixiaoshuai 这样的值,并得到对应行的在内存中的引用,明显要比扫描全表获得值为 leixiaoshuai 的行的方式快很多。

哈希索引的缺点

上面说了哈希索引的优点,那哈希索引的缺点也是绕不过去的。

哈希表是无顺的数据结构,对于很多类型的查询语句哈希索引都无能为力。举例来说,假如你想要找出所有小于40岁的员工。你怎么使用使用哈希索引进行查询?这不可行,因为哈希表只适合查询键值对,也就是说查询相等的查询(例:like “WHERE name = ‘leixiaoshuai’)。哈希表的键值映射也暗示其键的存储是无序的。这就是为什么哈希索引通常不是数据库索引的默认数据结构,因为在作为索引的数据结构时,其不像B+Tree那么灵活

总结一下缺点:

  • (1)不支持范围查询
  • (2)不支持索引完成排序
  • (3)不支持联合索引的左前缀匹配规则

还有什么其他类型的索引?

常见的还有:R 树和位图索引。

R 树通常用来为空间问题提供帮助。例如,一个查询要求“查询出所有距离我两公里之内的麦当劳”,如果数据库表使用R树索引,这类查询的效率将会提高。

位图索引(bitmap index), 这类索引适合放在包含布尔值(true 和 false)的列上。

索引如何提高性能?

因为索引基本上是用来存储列值的数据结构,这使查找这些列值更加快速。如果索引使用B+树数据结构,那么其中的数据是有序的,有序的列值可以极大的提升性能。

假如我们在 name 这一列上创建一个 B+树 索引,这意味着当我们用之前的SQL查找name=‘leixiaoshuai‘时不需要再扫描全表,而是用索引查找去查找名字为‘leixiaoshuai’的员工,因为索引已经按照按字母顺序排序。索引已经排序意味着查询一个名字会快很多,因为名字少字母为‘L’的员工都是排列在一起的。另外重要的一点是,索引同时存储了表中相应行的指针以获取其他列的数据。

数据库索引中到底存的是什么?

你现在已经知道数据库索引是创建在表的某列上的,并且存储了这一列的所有值。但是需要理解的重点是数据库索引并不存储这个表中其他列(字段)的值。举例来说,如果我们在 name 列创建索引,那么 age 列和 address 列上的值并不会存储在这个索引当中。如果我们确实把其他所有字段也存储在个这个索引中,那这样会占用太大的空间而且会十分低效。

索引还存储指向表行的指针

如果我们在索引里找到某一条记录作为索引的列的值,如何才能找到这一条记录的其它值呢?

这很简单,数据库索引同时存储了指向表中的相应行的指针。指针是指一块内存区域, 该内存区域记录的是对硬盘上记录的相应行的数据的引用。因此,索引中除了存储列的值,还存储着一个指向在行数据的索引。也就是说,索引中的name这列的某个值(或者节点)可以描述为 (“leixiaoshuai”, 0x996996), 0x996996 就是包含 “leixiaoshuai”那行数据在硬盘上的地址。如果没有这个引用,你就只能访问到一个单独的值(“leixiaoshuai”),而这样没有意义,因为你不能获取这一行记录的employee的其他值-例如地址(address)和年龄(age)。

数据库如何知道何时使用索引?

当你运行一条查询 SQL 语句时,数据库会检查在查询的列上是否有索引。假设 name 列上确实创建了索引,数据库会接着检查使用这个索引做查询是否合理 ,因为有些场景下,使用索引比起全表扫描会更加低效。

可以强制数据库在查询中使用索引吗?

通常来说, 你不会告诉数据库什么时候使用索引,数据库自己决定。

如何在SQL中创建索引?

下面是在前面示例中的Employee_Name列上创建索引时实际SQL的外观:

CREATE INDEX name_index
ON t_employee (name)

如何在SQL中创建联合(多列)索引?

我们可以在age 和 address 两列上创建联合索引,SQL如下:

CREATE INDEX age_address_index
ON t_employee (age, address)

可以把数据库索引类比成什么?

一个非常好的类比是把数据库索引看作是书的索引。

你从头到尾逐字逐行读完就是「全表扫描」;

你翻看目录挑选感兴趣的部分阅读就是走了索引。

使用数据库索引有什么代价?

既然索引优点这么多,那给所有列加上索引不就完事了,no no no,加索引是有代价的。

(1)索引会占用空间。你的表越大,索引占用的空间越大。

(2)在更新操作有性能损失。当你在表中添加、删除或者更新行数据的时候, 在索引中也会有相同的操作。

基本原则是:如果表中某列在查询过程中使用的非常频繁,那就在该列上创建索引


参考:

  1. How do database indexes work? And, how do indexes help? Provide a tutorial on database indexes.

  2. 数据库索引漫谈



相关文章