数据库索引如何工作?
0 397
1
该提问暂无详细描述
收藏
2021-02-05 16:21 更新 玩手机的豆浆 •  539
共 1 个回答
高赞 时间
0

为什么需要它?

当数据存储在基于磁盘的存储设备上时,它将作为数据块存储。完全访问这些块,使它们成为原子磁盘访问操作。磁盘块的结构与链接列表几乎相同。两者都包含一个数据节,一个指向下一个节点(或块)位置的指针,并且都不需要连续存储。

由于许多记录只能在一个字段上排序,因此我们可以说,在未排序的字段上进行搜索需要进行线性搜索,而线性搜索需要进行N/2块访问(平均),请问其中N的块数表跨度。如果该字段是非关键字段(即不包含唯一条目),则必须在N块访问时搜索整个表空间。

而对于已排序的字段,可以使用具有log2 N块访问权限的二进制搜索。同样,由于给定的非键字段对数据进行了排序,一旦找到更高的值,就不需要在表的其余部分中搜索重复的值。因此,性能提升非常明显。

什么是索引?

索引是对多个字段上的多个记录进行排序的一种方式。在表中的字段上创建索引会创建另一个数据结构,该数据结构保存该字段值以及指向与其相关的记录的指针。然后对该索引结构进行排序,从而允许对其执行二进制搜索。

索引的不利之处在于,由于使用MyISAM引擎将索引一起存储在表中,因此这些索引需要磁盘上的额外空间,如果对同一表中的许多字段进行了索引,则此文件可以快速达到基础文件系统的大小限制。

它是如何工作的?

首先,让我们概述一个示例数据库表架构;

字段名称数据类型磁盘大小 id(主键)无符号INT 4字节 firstName Char(50)50个字节 姓氏Char(50)50字节 emailAddress Char(100)100字节 注意:使用char代替varchar可以精确计算磁盘大小。该示例数据库包含五百万行,并且没有索引。现在将分析几个查询的性能。这些是使用id(已排序关键字字段)的查询,以及使用firstName(非关键未排序字段)的查询。

实施例1 -排序VS未排序的字段

给定我们的样本数据库,r = 5,000,000记录大小固定,给出记录的R = 204字节长度,并且使用MyISAM引擎将它们存储在表中,该引擎使用默认的块大小B = 1,024字节。该表的阻塞因素是bfr = (B/R) = 1024/204 = 5每个磁盘块的记录。保存该表所需的总块数为N = (r/bfr) = 5000000/5 = 1,000,000块。

N/2 = 500,000假定id字段是键字段,则对id字段进行线性搜索将需要平均块访问才能找到一个值。但是,由于id字段也已排序,因此可以进行二进制搜索,需要对log2 1000000 = 19.93 = 20块访问进行平均。立刻我们可以看到这是一个巨大的进步。

现在,firstName字段既没有排序,也没有关键字字段,因此二进制搜索是不可能的,值也不是唯一的,因此表将需要搜索到末尾以进行精确的N = 1,000,000块访问。索引旨在纠正这种情况。

假定索引记录仅包含索引字段和指向原始记录的指针,则可以认为它会小于它指向的多字段记录。因此,索引本身比原始表需要更少的磁盘块,因此需要更少的块访问来进行迭代。下面概述了firstName字段上的索引的架构;

字段名称数据类型磁盘大小
firstName Char(50)50个字节
(记录指针)特殊的4个字节

注意: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%,查询优化器将避免使用索引,有效地使索引浪费空间。

收藏
2021-02-05 16:22 更新 han •  235