好问题
Good  Question
  • 首 页
  • 问题
    • PHP
    • JAVA
    • CPlusPlus
    • C#
    • SQL
  • 关 于
  • 联 系
数据库索引如何工作? 关闭 返回上一级  

数据库索引如何工作?
+ 查看更多

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

最新文章

  • 函数`__construct`用来干嘛的
    发布日期:2018-03-26
  • 通过访客的IP得到他们的地区
    发布日期:2018-03-26
  • 合并两个PHP对象的最好的方法是什么?
    发布日期:2018-03-26
  • 该如何把一该如何把一个对象转化成数组?
    发布日期:2018-03-26
  • 什么是输出缓冲区?
    发布日期:2018-03-26
  • 在PHP中怎么把用逗号分隔的字符串分隔在一个数组里?
    发布日期:2018-03-26
  • 在PHP中使用foreach循环时查找数组的最后一个元素
    发布日期:2018-03-26
关于好问
收集整理一些有用的问题和回答,造福中国的程序旺和IT喵们!
友情链接
起飞页 
相关信息
版权声明
Copyright © 2016 - 2022  苏州卡达网络科技有限公司 备案号:苏ICP备09008221号