xiaoyh 的个人博客

一个只会敲代码的咸鱼

0%

面试 —— 索引

发表于 更新于 分类于

索引是什么

以字典为例，普通的数据库查找，就如同从字典的第一页往后翻去找一个字一样，需要从数据表的第一行开始顺序查找下去。表越大，消耗的时间就越长。

因此查阅字典一般都是通过目录直接定位到查找的值，索引可以理解为数据库的目录，用于提高数据库的查阅速度。

索引的优缺点

优点：提高了数据库的查询效率；

缺点：会降低数据库更新的效率，因为需要修改索引文件。

索引的底层实现原理

索引有两种： BTREE 和 HASH。MyISAM 和 InnoDB 只支持 BTREE 索引；MEMORY 都支持，默认 HASH。

写在前面：磁盘 IO 与预读

磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘 IO 的时间，大概 9ms，这个成本是访问内存的十万倍左右。

正是由于磁盘 IO 是非常昂贵的操作，所以计算机操作系统对此做了优化：预读。每一次 IO 时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。

每次磁盘 IO 读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为 4k 或者 8k 。这也就意味着发生一次磁盘 IO 时实际会读取一页的数据。

什么是 BTREE

BTREE 也叫 B 树，是一种多路平衡树。MySQL 的底层实现是 B+ 树。

B 树与 B+ 树的区别

  1. B 树的子节点处于父节点所表示的开区间内，不包含父节点的值；
    B+ 树的子节点处于父节点所表示的闭区间中，且一定包含父节点的值；
  2. B 树的信息包含于每个节点。
    B+ 树的信息全部包含于叶节点，且叶节点相连组成一个有序链表；

一些问题

为什么使用 BTREE 而不是 HASH

  1. 从内存角度上，数据库中的索引一般在磁盘上，数据量大的情况下会发生多次磁盘 IO，BTREE 的设计可以允许数据分批加载，极大地降低磁盘 IO 的次数；
  2. 从业务场景上说，Hash 索引不能范围查询，因为经过 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和 Hash 运算前完全一样；
  3. 对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，所以只使用组合索引中的部分索引进行查询时无法走索引，不支持最左前缀匹配原则；
  4. HASH 冲突导致 HASH 索引无法避免表扫描且降低搜索效率。

为什么不用红黑树

树的查询时间跟树的高度有关，B+ 树是一棵多路搜索树，可以降低树的高度，提高查找效率。

能否无限增加树的路数提高查找效率

之所以设计成 BTREE，就是为了分批加载索引。如果设计成很多条路数，这样在某个节点会形成一个庞大的有序数组，可能不能一次性从磁盘加载到内存中。

为什么用 B+ 树不用 B 树

数据库中 select 数据，不一定只选一条，很多时候会选中多条，比如选前 100 条数据，对于 B 树就得在找到起点后中序遍历，可能要跨层访问。而 B+ 树由于所有的数据都在叶节点不用跨层，直接通过链表就能取出前 100 条数据。

索引分类

MYSQL的索引主要分为普通索引、唯一索引、组合索引、主键索引（PRIMARY KEY）、全文索引（FULLTEXT）。

  • 普通索引：是最基本的索引，没有限制。
  • 唯一索引：唯一索引不允许索引列有重复值，允许有空值。
  • 主键索引：它是一种特殊的唯一索引，不允许有空值。在建表的时候若指定了主键，就会自动创建主键索引。
  • 全文索引：全文索引，就是全文搜索中搜索某个关键词，比模糊查询要快得多，仅适用于 CHAR， VARCHAR 和 TEXT 列。

主键索引与唯一索引的区别

  1. 主键是一种约束，而唯一索引是一种索引，是表的冗余数据结构，两者有本质的差别；
  2. 主键一定会创建一个唯一索引，但是有唯一索引的列不一定是主键；
  3. 一个表只能有一个主键，但是可以有多个唯一索引；

多列索引

以索引包含的列数划分，索引可以是单列索引，也可以是多列索引（也叫组合索引等）。

若多列索引是唯一索引，则该索引的组合不能重复。

最左前缀原则

在建立多列索引时需要规定索引列的顺序，比如对列 a，b，c 建立多列索引 (a, b, c)。

在此情况下，查询条件必须符合索引建立的顺序才能走索引查询。

比如以下的查询语句并不会去查询索引树：

1
2
select * from table_name where c<1;
select * from table_name where b<1 and c<2;

以下三种才会走索引：

1
2
3
select * from table where a<1;
select * from table where a<1 and b<2;
select * from table where a<1 and b<2 and c<3;

可以看出，所有走索引的查询语句都带有 a 字段。

当创建形如 (a, b, c) 的多列索引，相当于创建了 (a) 单列索引，(a, b) 多列索引以及 (a, b, c) 多列索引，这就是最左前缀原则。

多列索引的最左前缀原则导致其一个索引与多个索引等效，降低了磁盘空间的开销。

对于如下的查询语句：

1
select * from table where a<1 and c<2;

只会走 (a) 的单列索引，而不会走 c 。

= 和 IN 可以乱序，MySQL 的查询优化器会为此做优化。

全文索引

如果希望通过关键字的匹配来进行查询，那么就需要基于相似度的查询。全文索引就是为这种场景设计的。

与 LIKE 模糊匹配相比，全文索引要快很多，但是可能存在精度问题。

MySQL 中的全文索引，有两个变量：最小搜索长度和最大搜索长度。

对于长度小于最小搜索长度和大于最大搜索长度的词语，都不会走索引。通俗点说，想对一个词语使用全文索引搜索，那么这个词语的长度必须在以上两个变量的区间内。

聚集索引与非聚集索引

聚集（clustered）索引的逻辑顺序与磁盘上数据行的物理存储顺序相同，一个表中只能拥有一个聚集索引。

非聚集索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

聚集索引就像是字典的拼音目录，拼音目录对应的 A-Z 的字顺序，和字典实际存储的字的顺序 A-Z 也是一样的，A 开头的字的后面一定是 B 开头的字。如果想插入一个 B 开头的字，那么肯定会按照拼音目录插到 A 开头的字的后面。

非聚集索引就像字典的偏旁目录，它的顺序与实际存放顺序不一定一致。比如偏旁艹下面依次放着艺、劳、若，其对应的页数分别是 568，279，419，存储顺序并不是连续的。

主键索引与聚集索引的关系

在 MySQL 的 InnoDB 引擎中，主键索引就是聚集索引。

但在 MyISAM 引擎里主键不是聚集索引。

在 SQL Server 中，也是默认主键为聚集索引，但是可以显式的指定聚集索引。

聚集索引决定了数据库的物理存储结构，而主键只是确定表格的逻辑组织方式。这两者不可混淆！

对于 InnoDB ：

  1. 如果一个主键被定义了，那么这个主键就是聚集索引;
  2. 如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引；
  3. 如果没有主键也没有合适的唯一索引，那么 InnoDB 内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个 6 字节的自增列；

为什么推荐把自增主键作为聚集索引

自增主键会把数据自动向后插入，避免了插入过程中的聚集索引的排序问题。

聚集索引的排序，必然会带来大范围的数据的物理移动，这里面带来的磁盘 IO 性能损耗是非常大的。

而如果聚集索引上的值可以改动的话，那么也会触发物理磁盘上的移动，所以也不应该修改聚集索引。

非聚集索引的二次查找问题

对于 InnoDB ，非聚集索引存储的是主键（聚集索引），所以通过非聚集索引查询时，第一次查询是通过非聚集索引找到主键，第二次查询是通过主键找到对应的行位置。

不过，如果查找时只查找非聚集索引本身或者主键，就不会触发第二次查询，这称之为索引覆盖：

1
select id, index_name from table_name where index_name='abc';

可以通过组合索引，把想要查询的列包含进非聚集索引，就不会触发二次查询。