发布日期:2018-03-26
数据库索引如何工作?+ 查看更多
数据库索引如何工作?
+ 查看更多
发布日期:2018-02-23 10:07
分类:SQL
浏览次数:198
考虑到当你的数据集在容量上增加时索引如此重要,有人能从数据库不可知级别解释一下索引是如何工作的吗?
关于索引字段查询的信息,请参阅另一个问题“我如何进行数据表列的索引”。
回答:
为什么需要它?
当数据基于存储设备存储在磁盘上时,它作为数据块进行存储。这些数据块被整体地存取,使得在进行磁盘存取操作时保持其原子性。磁盘存储块组织构成的方式和链表一样;都包含用于数据的部分和一个指向下一个结点位置的指针(或下一个块),并且都不需要连续存储。
因为多个记录只能在一个字段上排序,我们可以声明,在对未排序的字段进行搜索时需要使用线性搜索,它需要对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%,查询优化器将避免使用索引,因为实际上这种情况下建立索引是对空间的浪费。