SQL索引, since 2022-04-14

作者: Mc杰夫 | 来源:发表于2022-04-14 16:01 被阅读0次

(2022.04.14 Thur)

SQL在执行检索或更新时，会对全表进行遍历操作。而这种操作会浪费大量时间。索引(index)的使用极大的提升了数据查询的效率。

索引也是一个表，只是这个表对用户不可见，仅仅在执行对关系的查询和修改时调用。索引这个表包含被索引的字段、该字段的不同值和指向不同值的指针(pointer)。

索引可以针对一个列，可以针对多列，也包括对不同列的组合。

索引可以极大的提高查询的性能，但是限制关系的更新速度。一个关系设定的索引越多，更新关系时的速度就越慢。一般来说一个关系的索引不超过6个。

MySQL支持的索引类型

(2022.06.17 Fri)
在MySQL中，索引是在存储引擎层而非服务器层实现，没有统一的索引标准，不同存储引擎的索引工作方式不同，不是所有存储引擎都支持所有类型的索引，同一种索引类型，不同存储引擎的底层实现也可能不同。

这里主要介绍MySQL中的B-tree索引和哈希索引，其他的诸如全文索引、空间数据索引等略。

B-tree索引

当人们谈论索引，如果没有特别指明，说的就是B-tree索引，它使用B-tree数据结构来存储数据。

B-tree意味着所有值都是按顺序存储的，每个叶子页到根的距离相同，这也是B-tree的特性。

Index based on B-tree

有了B-tree索引加持，检索不需要查询全表，仅需要从B-tree的根节点开始查询，B树的叶子节点定义了被索引量的上下限。最终存储引擎中找到查询值，或者不存在。

叶子节点存储的指针指向被索引的数据，而非其他叶节点。

B树的对被索引的序列按顺序组织存储，适合查找范围。而基于文本的索引树，按字母顺序传递连续的值进行查找也很合适。

除了单列，B树还可以对多列进行索引，比如下面这个表

CREATE TABLE people (
    last_name varchar(50) NOT NULL,
    family_name varchar(50) NOT NULL,
    dob date NOT NULL,
    gender enum('m', 'f') NOT NULL,
    key(last_name, first_name, dob)
);

索引中包含了三个列的值，在索引表中的表示如下

多列索引demo

索引中三个列的顺序就是CREATE TABLE时指定的列顺序。可以注意到最后两个key，他们的last_name和family_name相同，而dob不同。

使用B-tree索引的查询类型

全值匹配：匹配索引中的所有列
匹配最左前缀：只匹配索引中的第一列
匹配列前缀：只匹配某列值的开头部分，
匹配范围值：比如匹配family_name在某个范围间的人，也只使用了索引的第一列
精确匹配某一列并范围匹配另一列：比如精确匹配last_name列，并范围匹配family_name，比如family_name以字母K开头的所有名字
只访问索引的查询：只需要访问索引，不需要访问数据行

索引除了用于查询，也可用于ORDER BY操作。

在MySQL中查看索引键的组成，可通过

mysql> DESC table_name;
mysql> DESCRIBE table_name;
mysql> SHOW CREATE TABLE table_name;

查看建表信息。

B-tree实现的多键索引在查询时的限制：

如果不是按照索引的最左列开始查找，则无法使用索引。比如无法从上面的关系中利用索引找到特定名字的人和特定生日的人，因为这两个列不是最左边开始的列。也无法查找姓氏以某字母结尾的人
不能跳过索引的列做查询，比如指定last_name和dob的查询，因为跳过了family_name这一列，则dob列的条件无效，系统只使用last_name字段做查询
如果查询中有某个列的范围查询，则右边所有列无法使用索引查询。如WHERE last_name = "Smith" and family_name LIKE "*K*" AND dob = "2000-01-01"这个查询只使用了索引的前两列，因为family_name字段的查询是范围查询指令LIKE，其后的dob查询将无效。如果查询范围值有限，可以使用多个等于的条件代替范围查询，提高效率。

上面的结果可以看到，索引中列的顺序对于搜索很重要。优化索引的过程中，可以使用相同列不同顺序的索引来满足不同查询需求。

哈希索引Hash index

基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎会对所有的索引列计算一个哈希码hash code。哈希索引将所有的哈希码存储在索引中，在哈希表中保存指向每个行数据的指针。在MySQL中Memory引擎默认支持哈希索引。如果多个列的哈希值相同，索引会以链表的方式存储多个记录指针到同一个哈希表中。考虑下面的关系

CREATE TABLE testhash(
    fname varchar(50) NOT NULL,
    lname varchar(50) NOT NULL,
    key using hash(fname)
) ENGINE MEMORY;

使用假想的哈希函数f()，对关系中的列做索引有如下值

f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458

注意在关系中，这四个名字是按序排列的。哈希索引的数据结构如下

slot 槽	value 值
2323	指向第1行的指针
2458	指向第4行的指针
7437	指向第2行的指针
8784	指向第3行的指针

注意slot的编号是按序排列，但数据不按此顺序。
哈希索引的查询过程如下，有查询mysql> SELECT lname from testhash where lname = "Peter"

计算Peter的哈希值
利用上一步计算的哈希值到哈希索引的数据结构中找到对应的数据，得到该哈希值对应的指针
根据指针找到testhash中对应的数据，比较是否其lname是Peter，验证通过就可以查询和返回结果

哈希索引的速度很快，但也有如下限制：

哈希索引中只包含哈希值和行指针，不含存储的数据，因此不能以此来避免读取行，略微影响性能，但考虑到哈希索引应用于内存中的行数据，本身速度很快，因此哈希对性能的影响可忽略
哈希索引数据不是按照索引值顺序存储，无法用于排序
哈希索引不支持部分索引列匹配查找，
支持等值比较查询，不支持范围查询
访问速度快，除非哈希导致很多冲突。如果出现哈希冲突，存储引擎遍历链表中的所有行指针，逐行比较，直到找到所有符合条件的行

因为限制多，哈希索引只适合特定情况，比如指向和关联多个数据表的星形schema。

创建自定义哈希索引

如果存储引擎不支持哈希索引，可以自己创建。基于B-tree创建哈希索引，使用B-tree进行查找，但是使用哈希值而不是键本身进行索引查找，需要在where从句中手动指定哈希函数。

比如一个关系url，其中存储了大量url，且对应的值非常长。

mysql> SELECT id from url where url='http://www.baidu.com';

删除url列上的索引，创建一个新的索引，使用CRC32做哈希函数，可用如下方式查询

mysql> SELECT from url 
       where url='http://www.baidu.com' and 
       url_crc = CRC32('http://www.baidu.com')

这样的查询结果速度提升明显。

这个案例中的url_crc列需要手动维护，或使用触发器维护。创建表格的方式如下

CREATE TABLE url (
    id int unsigned NOT NULL auto_increment,
    url varchar(255) NOT NULL,
    url_crc  int unsigned NOT NULL DEFAULT 0,
    PRIMARY KEY(id)
);

之后创建触发器，可以在数据insert和update(代码中未展示)时加入url_crc对应的值。

DELIMITER//
CREATE TRIGGER pseudohash_crc_ins BEFORE INSERT ON pseudohash FOR EACH ROW BEGIN 
SET NEW.url_crc = CRC32(NEW.url);
END;
DELIMITER;

则每一次插入url数据时会自动生成url_crc字段并赋值。

如果数据大，则CRC32会产生大量哈希冲突，可以自定义哈希函数，利用MD5函数返回值的一部分做哈希

mysql> SELECT CONV(RIGHT(MD5('http://www.baidu.com'), 16), 16, 10) as hash64;

处理哈希冲突，可以在WHERE从句中除了包含哈希索引字段，还加入常量字段，共同检索。

mysql> SELECT id from url where url_crc = CRC32('http://www.baidu.com') 
       and url = 'http://www.baidu.com';

B-tree和hash index各自适合的场景

(2022.07.16 Sat)
能够应用B-tree的检索场景

全值匹配查询：where some_filed = 1980
最左前缀列的查询：由field_1和field_2做联合索引，只使用第一列查询可利用索引(或使用这两列做联合查询)
匹配列前缀查询：where some_field LIKE 'acd%'
匹配值的范围查询：where some_field > 1111 AND some_field < 2222
只访问索引的查询

限制使用B-tree的场景

NOT IN、IN和<>
如果查询中有某个列的范围查询，则其右边所有列都无法使用索引

Hash索引适用：

等值=，包含IN、NOT IN、不等<>

Hash索引的限制：

如果字段中有大量相同的值，将导致Hash冲突
不支持范围查询
一直要求全表扫描
必须进行二次查找
不支持用索引排序
不支持部分索引查找也不支持范围查找

索引类型

Unique
Primary key
Simple/Regular/Normal
Full-text

Unique索引

unique索引对应的单列，其值没有重复值，但可以有Null值。Unique索引对应的列对(column pair)，其中的某个单列可以有重复值，但是作为pair，应该没有完全重合的值，即可以(1, 1)和(1, 2)，而不可以(1, 1)和(1, 1)。

CREATE UNIQUE INDEX <index_name> ON <table_name>(<index_column1>, <index_column2>,…);
# or
CREATE TABLE <table_name>(<column1> CHAR (30) NOT NULL, UNIQUE INDEX (<column2>));
# or
ALTER TABLE <table_name> ADD UNIQUE INDEX (<column1>, <column2>);

Primary索引

Primary索引是一种unique索引，不同的是primary索引处理的列不能含有Null值，并且只能是单列(?)。一旦列的值确定，primary索引无法修改。

CREATE TABLE <table_name> (<column_name> <data_type> PRIMARY KEY );
# or
CREATE TABLE <table_name> (<column1> CHAR(30) NOT NULL, <column2> CHAR(30) NOT NULL, PRIMARY KEY (<column1>, <column2>));
# or
ALTER TABLE <table_name> ADD PRIMARY KEY(<column1>, <column2>);

Simple/Regular/Normal

这种常规的索引，被索引的列可以有重复值，可以有空值。这种索引目的在于提高查询速度。

CREATE INDEX <index_name> ON <table_name>  (<index_column1>, <index_column2>, …);
# or
CREATE TABLE <table_name>(<column1> CHAR(30) NOT NULL, INDEX(<column2>));
# or
ALTER TABLE <table_name> ADD INDEX(<column1>, <column2>);

Full-text

全文索引用于实现全文检索。适用的情况是在文本中所有特定关键词和特定substring，在搜索引擎和电子商务中应用广泛。这种索引仅适用于MySQLISAM和InnoDB，以及VARCHAR，CHAR和Text类型的列。

适用与不适用的情况

适用的情况

(被索引的)列含有大量不同的值
列不含大量空值
单列或多列在WHERE或JOIN语句中被频繁使用

不适用的情况

表不大
在检索中，列不常被当做检索条件
列频繁更新

(2022.04.15 Fri)

计算最佳索引

建立的索引越多，对给定的查询来说，更有可能提高访问速度，但同时会降低更新的速度。每个对于关系R的更新操作会迫使同时更新R修改过的属性或者属性集上的索引，即不仅要读取和回写修改的R的页，还需要花费额外代价读取和回写存储索引的页。实际上，更新操作本身页包含了对数据库的查询，比如带有select-from-where的子查询插入或者带条件的删除操作，也就是说索引的加入会影响更新的效率，但在建立索引时，仍需要考虑查询和更新的相对频度问题。

在做最佳索引分析之前，我们做如下假定：

关系被存储在很多磁盘块(页)上，索引页被保存在磁盘块页上
查询或更新的主要代价通常来自于将所需的磁盘页读入到主存的数目(次数)
对关系的访问和更新操作，过去和未来有着相似的操作频率，因此可以通过对过往的数据分析预测未来
数据库提供了某种工具，可以查看过去在数据库或关系上执行的查询和更新的代码
访问一个记录和访问记录所在页面的时间相差无几

下面通过一个实例来实现寻找最佳索引的过程。有一个关系StarsIn(movieTitle, movieYear, starName)。对这个关系有如下假定：

关系StartsIn存储在10个( $n_p$ )磁盘页中。在没有任何索引的情况要检查整个关系，需要遍历10页磁盘，则代价为10
平均每部电影包含3个( $n_m$ )影星，每个影星出现在3部电影中( $n_s$ )
考虑根据影星查找电影的情况，相关的元组随机分布在10个磁盘页中，即便已经根据影星建立索引，也需要3次磁盘访问才能找出该影星的3个元组。如果没有索引，需要10次磁盘访问操作
假定某属性已经加索引，为了利用该属性上的索引定位对应元组，每次需要一次磁盘访问将索引所在的页读入主存(进而访问该属性)。如果索引页需要更新(插入或其他)，还需要一次磁盘访问将改变后的索引写回磁盘
对某有索引的属性执行插入或其他更新，需要一次磁盘访问读取用于容纳新元组的磁盘也，再花费一次磁盘访问用于回写这个磁盘页。假定即使在没有索引的情况下，不需要扫描整个关系，就能找到用于添加新元组的磁盘页

下面分析不同操作的代价，一个代价代表着访问一次磁盘页面。考虑到访问记录和访问磁盘的时间相差不多，以访问磁盘页面为代价计算标准。

这里使用两种查询，1) 给定影星信息的查询Q1，2) 给定电影信息的查询Q2。一种修改，即对关系R做插入操作I。

不使用索引，Q1和Q2都需要对整个关系做扫描，代价均为10. I需要读取一个有空闲空间的硬盘页( $n_I$ )，再将新的元组写入，代价是2.

使用索引，仅对starName属性做索引，Q2仍需扫描整个关系，代价为10.而Q1通过访问1次索引页( $n_{ind}$ )快速找到给定影星对应的3个元组，再通过3次磁盘访问将包含3个元组的磁盘页读入主存，因此累计代价为4.插入操作I对索引页和数据页都进行一次读入操作和回写操作，需要4次磁盘访问，代价为4.

仅对movieName属性做索引的情况和前一种情况相同。

如果对starName和movieName都做索引，则Q1和Q2都需要4次访问磁盘其中含一次索引，即代价各为4。而插入操作需要分别对两个索引表进行访问和修改，外加对数据页做读写操作，累计6次访问。

同时，假定Q1在总的操作中的时间比例是 $p1$ ，Q2的比例是 $p2$ ，I的比例是 $1-p1-p2$ 。

每种情况对应的总时间代价在下面表中列出。

action	No Index	Star Index	Movie Index	Both Indexes
Q1	10: $n_p$	4: $n_{ind}+n_s$	10: $n_p$	4: $n_{ind}+n_s$
Q2	10: $n_p$	10: $n_p$	4: $n_{ind} + n_m$	4: $n_{ind}+n_m$
I	2: $n_I \times 2$	4: $n_{ind}\times 2+n_I \times 2$	4: $n_{ind}\times 2+n_I \times 2$	6: $n_{ind}\times 2 \times 2+ n_I \times 2$
cost	$2+8p1+8p2$	$4+6p2$	$4+6p1$	$6-2p1-2p2$