随笔录
0%

循序渐进理解索引机制

发表于 分类于 Valine：
本文字数： 3k 阅读时长 ≈ 8 分钟

前言

索引还是本科数据库课程教的东西，这里复习下，并从自己的角度做了份笔记。考虑到我自己的情况，这里假设数据结构中的哈希表、AVL树、B树、B+树都是已知的。

起源

需求

首先，我们假设我们需要在一个数据库中查询某个值，数据库应该如何完成这一过程。
而查询的过程不可能将整个索引都加载进内存，只能从硬盘分块逐一加载进内存，所以我们用硬盘I/O次数来衡量索引的优劣。

最原始的方法

最简单粗暴的方法就是从表头开始，挨个比对。
比如我们要在字典中查询mysql这个词，那么需要从a开头的abandon开始挨个翻到m开头的单词，然后再从第二个字母为a的开始，直到y，后面的sql也是一样的。如果是z开头的，那就得翻完几乎整本字典了。
该方法的时间复杂度是O(N)，在平常写算法时似乎还能接受，但在生产中，如果数据量达到千万的级别，那因为这个查询带来的用户量流失肯定是不容忽视的。

哈希表

既然简单粗暴的O(N)不行，那就O(1)呗，每个值都建一张哈希表得了。这么做带来的额外空间开销是O(N)，但时间复杂度直接降到了O(1)。可即便是大公司不在乎这点存储开销，但总感觉哪里不太对劲。
嗷，对了，哈希只能精确匹配。即哈希是需要根据key计算存储数据的地址，如果给的不少一个明确的值，那么哈希表这种方式就失去了效果。
换句话说，哈希只适用于where column.val = search.val的情况，并不能应付范围查询(>,<,between)、模糊查询(like)、并集查询(or)等情况。

自平衡二叉查找树

回忆数据结构的知识，灵光一闪，似乎我们可以用自平衡二叉搜索(AVL)树来建立索引。

AVL树中所有的结点都存储数据，红黑树就是一种弱平衡二叉树，其要求任一路径的查找长度不会超过其他任一路径的两倍，其平均I/O次数为 ，这似乎可以接受。但有没有更加高效的方法呢？

B树

与AVL树不同的是，B树每个父节点并不只有2个子节点。回顾B树的定义:

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特性的m叉树：

  1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字
  2. 若根结点不是终端结点，则至少有两颗子树。
  3. 除根节点外所有的非叶结点至少有 棵子树，即至少含有 个关键字。
  4. 所有非叶结点的结构如下：

    其中$K_i (i=1,2,...,n)$为结点的关键字，且满足 , 为指向子树根结点的指针，且以 为根节点的子树中 所有结点的关键字均大于 。n为结点中关键字的个数。
  5. 所有的叶节点出现在同一层。

    综上，m阶B树的I/O次数为
    B树通过增加每个结点存储索引，降低了磁盘I/O次数，在精确匹配时比AVL树更快，因此具有比AVL树更优的性能。
    ⚠️但由于B树的非叶子结点也存有数据，因此在做范围查询时，需要和AVL树一样做回旋查找。

B+树

一颗m阶的B+树满足下列条件：

  1. 每个分支结点最多有m棵子树。
  2. 非叶根结点至少有两颗子树，其他每个分支结点至少有 棵子树。
  3. 结点的子树个数与关键字个数相等。
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶节点按大小顺序相互链接起来。
  5. 所有分支结点（可以视为索引的索引）中仅包含他的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

回忆计算机操作系统——内存管理——虚拟内存管理的相关知识，一般是用分页的方式进行I/O。假设一种关键字长度较大，那么B树中页表中指正占比就减少，就需要更多的I/O次数。而由于B+树的结点只存指针，不存关键字，那么效率将会更高。
此外，由于B+树在叶子结点中存在顺序链接，因此做范围查找时不需要对父节点进行回旋查找，所以比B树有更优的性能。
⚠️事实上，Mysql对B+树索引做了改动，将叶子结点的单向指针改为了双向指针，因此做范围查找时，能应付更多的情况。（如果叶子结点指针方向为升序，那么在<=这样的查找操作时，效率退化严重）。
综上，数据库索引大多采用B+树。

分类

接下来，我们对索引进行细分。

普通索引

普通索引就是最基础的索引，它的值可以为空，可以不唯一，其存在的价值仅在于提高查询速度。
以Mysql为例，为某个字段建立普通索引只需要

1
creat index index_name on table_name(column_name(length));

唯一索引

顾名思义，唯一索引要求索引值必须唯一，但允许有空值。
其创建方式为：

1
creat unique index index_name on table_name(column_name(length));

主键索引

主键索引是一种唯一索引，要求索引值唯一，且不能为空。换句话说，指定为primary key的即是主键索引，每个表只能有一个主键。⚠️实际生成中的主键可能是有多个关键字组成。
需要说明一下，主键约束与唯一索引之间并没有很大的差别。比如IBM DB2的文档中就提到：

了解主唯一键约束与唯一索引之间没有很大差别这一点很重要。数据库管理器使用唯一索引和 NOT NULL 约束的组合来实现主键约束和唯一键约束的关系数据库概念。因此，唯一索引本身不强制执行主键约束，因为它们允许空值。（虽然空值表示未知值，但在建立索引时，将一个空值视为与其他空值相同。）
因此，如果唯一索引由单个列组成，那么只允许一个空值 - 多个空值将违反唯一约束。同样，如果唯一索引由多个列组成，那么值和空值的特定组合只能使用一次。

全文索引

全文索引的索引类型为FULLTEXT。全文索引可以在varchar、char、text类型的列上创建。

组合索引

即多个关键字组成一个索引，专门用于组合搜索。

存储方式

聚蔟索引

聚簇索引并不是一种单独的索引类型，而是对磁盘上实际数据重新组织以按指定的一个或多个列的值顺序存储的算法。特点是存储数据的顺序与索引顺序一致，且一张表只允许存在一个聚簇索引（因为数据一旦存储，顺序只能有一种）。
可以把聚簇索引类比成Array，数据的物理存放顺序与索引顺序一致，索引相邻的数据也相邻（相邻的数据在同一页中）。考虑到插入与删除操作带来的问题，使用聚簇索引方式要求索引是自增ID的主键。
⚠️聚簇索引的叶子结点就是数据结点。

非聚簇索引

而非聚簇索引就是将数据和索引的叶子结点分离，叶子结点并不指向数据的对应行，而是存储该数据块的指针。
因此，一张表可以有多个非聚簇索引。

区别与联系

聚簇索引和非聚簇索引对应的都是B+树结构。
以下是聚簇索引和非聚簇索引检索过程的区别图示：

可以看出，在InnoDB中，只有主键索引被建立为聚簇索引，辅助键索引采用的是非聚簇索引，其叶子结点的数据是主键，然后再根据主键完成一次主键索引，以获得整条数据(这一过程称为回表)。
而在MyISAM中，主键索引和辅助键索引都是非聚簇索引，其叶子结点中存储的是数据对应的地址。
综上，我们总结出如下区别：

  • InnoDB中，聚簇索引是用来保存数据的，而非聚簇索引的目的仅仅是加快查询速度
  • 聚簇索引唯一，非聚簇索引不唯一。一个InnoDB表只有一个聚簇索引，如果没有显式声明，那么InnoDB就会自动添加一个。而InnoDB默认并不会创建任何非聚簇索引。
-------------------本文结束 感谢阅读-------------------