发布日期：2018-03-26
数据库索引如何工作？+ 查看更多
数据库索引如何工作？
+ 查看更多
发布日期：2018-02-23 10:07
分类：SQL
浏览次数：74
考虑到当你的数据集在容量上增加时索引如此重要，有人能从数据库不可知级别解释一下索引是如何工作的吗？
关于索引字段查询的信息，请参阅另一个问题“我如何进行数据表列的索引”。
回答:
为什么需要它？
当数据基于存储设备存储在磁盘上时，它作为数据块进行存储。这些数据块被整体地存取，使得在进行磁盘存取操作时保持其原子性。磁盘存储块组织构成的方式和链表一样；都包含用于数据的部分和一个指向下一个结点位置的指针（或下一个块），并且都不需要连续存储。
因为多个记录只能在一个字段上排序，我们可以声明，在对未排序的字段进行搜索时需要使用线性搜索，它需要对N/2数据块进行存取（平均上），N表示数据块的表跨度。如果该字段并不是关键字（即不包含唯一条目），则整个表空间会被搜索访问N数据块。
而对于排好序的字段，二分查找可能会被用到，将存取log2N 数据块。此外，由于数据是根据非关键字字段进行排序的，当找到较高的值时，表的剩余部分就不需要再被搜索重复值。因此，性能的增加是显著的。
什么是索引？
索引是一种在多个字段上对多个记录进行排序的方法。在表中的字段上创建索引会创建另一个数据结构，它会保存字段值以及指向与它相关的记录的指针。然后这个索引结构会进行排序，允许对其执行二分搜索。
索引的缺点是这些索引需要在磁盘上额外开辟新的空间，因为索引使用MyISAM引擎存储在一个表中，如果同一个表中有多个字段被索引，这个文件可以快速到达基础文件系统的大小限制。
它是如何工作的？
首先，让我们概述一个作为示例的数据库表模式；Field name Data type Size on disk id (Primary key) Unsigned INT 4 bytes firstName Char(50) 50 bytes lastName Char(50) 50 bytes emailAddress Char(100) 100 bytes
注意：
考虑到磁盘值的精确大小，用定长字符型代替变长字符型。此样本数据库包含500万行，并且未被索引。现在来分析几个查询的性能。其中一个查询使用id（一个排好序的主键），一个使用firstName（未被排序的非主键字段）。
例1-排好序字段vs未排序字段
假设有
r = 5,000,000
条固定大小的记录的样本数据库，以及给每条记录R=204字节，使用默认块大小为
B=1024
字节的MyISAM引擎将它们存储在一张表中。表的块因子会是
bfr = (B/R) = 1024/204 = 5
记录/磁盘块。保存表所需的块的总数是
N = (r/bfr) = 5000000/5 = 1,000,000
块。
对id字段的线性搜索来说，考虑到它是关键字，找到一个值平均需要对
N/2 = 500,000
块进行访问。但是因为它被排序，可以执行平均需要
Nlog2 1000000 = 19.93 = 20
块的数据块访问的二分搜索。瞬间我们可以看到这是一个很大改善。
现在firstName既没有被排序，也不是关键字段，所以无法进行二分搜索，并且值并不是唯一的，因此这个表需要精确搜索到
N = 1,000,000
块存取的最后。索引的目的就是为了改善这种情况。
假设一条索引记录只包含被索引的字段和一个指向原始记录的指针，它的存在是有道理的，它比它指向的多字段记录小。所以索引本身比原始表需要更少的磁盘块，因此它循环访问需要更少的块存取。对字段firstName进行索引的模式描述如下：
Field name Data type Size on disk firstName Char(50) 50 bytes (record pointer) Special 4 bytes
注意：
在MySQL上指针长度为2,3,4或5个字节，具体取决于表的大小。
例2-索引
假设我们的示例数据库有
r = 5,000,000
条记录，一条索引记录的长度为
R = 54
字节，默认数据块的大小为
B = 1,024
字节。索引的块因子会是
bfr = (B/R) = 1024/54 = 18
条记录/磁盘块 。保存索引总共需要
N = (r/bfr) = 5000000/18 = 277,778
个数据块。
现在使用firstName字段的查询可以利用索引来提高性能。考虑到对索引的二分搜索平均上需要进行
log2 277778 = 18.08 = 19
块的访问。为了找到实际记录的地址，需要再进一步访问一个块来读取数据，使得一共要进行
19 + 1 = 20
块的访问，这个数据远比在一个无索引的表中对firstName字段进行匹配所需的1,000,000块的访问好太多了。
何时使用索引？
考虑到创建索引需要额外的磁盘空间（在上面的例子中需要额外277,778个块，增加了约28%），并且太多的索引可能因为文件系统大小的限制而引起问题，必须仔细考虑选择正确地字段进行索引。
因为索引仅用于加速搜索在记录内的匹配字段，所以当进行一个插入或删除操作时，索引字段仅用于输出是对磁盘空间和处理时间的浪费，因此这种行为应该被避免。基于二分搜索的性质，数据的基数和唯一性很重要。对基础为2的字段进行索引，会将数据拆分为一半，然而基数为1,000的数据将返回大约1,000条记录。在如此低的基数下，有效性会被降低到线性排序，并且如果基础小于记录数的30%，查询优化器将避免使用索引，因为实际上这种情况下建立索引是对空间的浪费。