数据库索引如何工作?

鉴于索引是非常重要的,因为你的数据集的规模增加了,有人可以解释索引如何在数据库无关的层面上工作吗?

有关索引字段的查询的信息,请查看如何索引数据库列

答案


为什么需要?

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

由于许多记录只能在一个字段上排序,所以我们可以声明,在未排序的字段上搜索需要线性搜索,它需要N/2块访问(平均),N块的数量在哪里桌子横跨。如果该字段是非关键字段(即不包含唯一条目),则必须在N块访问时搜索整个表空间。

而对于排序的字段,可以使用二进制搜索,其具有log2 N块访问。此外,由于数据是在给定非关键字段的情况下进行排序的,因此一旦找到更高的值,表格的其余部分就不需要搜索重复值。因此,性能增加是相当大的。

什么是索引?

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

索引的缺点是这些索引在磁盘上需要额外的空间,因为索引使用MyISAM引擎一起存储在一个表中,如果同一个表中的许多字段是相同的,那么该文件可以快速达到底层文件系统的大小限制索引。

它是如何工作的?

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

字段名称数据类型磁盘上的大小
id(主键)无符号整数4字节
firstName Char(50)50个字节
姓氏字符(50)50个字节
emailAddress字符(100)100个字节

注意:字符被用来代替varchar以允许磁盘值的准确大小。此样本数据库包含500万行,并且未进行索引。现在将分析几个查询的性能。这些是使用id(排序的关键字段)的查询和使用firstName(非关键字未排序的字段)的查询。

示例1 –分类与未排序的字段

鉴于我们的示例数据库中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,000id字段是关键字段,那么对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%,查询优化器将避免使用索引,从而有效地使索引浪费空间。


我第一次读这篇文章对我非常有帮助。谢谢。

从那以后,我对创建索引的缺点有了一些了解:如果您使用一个索引写入表(UPDATEINSERT),则实际上在文件系统中有两个写操作。一个用于表格数据,另一个用于索引数据(以及对它的引用(以及 – 如果聚集 – 表格数据的求和))。如果表和索引位于同一块硬盘上,则花费更多时间。因此,没有索引(堆)的表将允许更快的写入操作。(如果你有两个索引,最终会有三个写操作,依此类推)

但是,在两个不同的硬盘上为索引数据和表格数据定义两个不同的位置可以减少/消除增加时间成本的问题。这需要在所需硬盘上定义附加文件组和相应文件,并根据需要定义表格/索引位置。

索引的另一个问题是插入数据时随时间的碎片。REORGANIZE帮助,你必须编写例程来完成它。

在某些情况下,堆比带索引的表更有用,

例如: – 如果您有很多相对的写作,但只有一个晚上在工作时间以外进行报告。

而且,聚集索引和非聚集索引之间的区别也非常重要。

帮助我: – 聚集索引和非聚集索引实际上意味着什么?


 

索引只是一种数据结构,可以使数据库中特定列的搜索速度更快。这个结构通常是一个B树或一个哈希表,但它可以是任何其他的逻辑结构。

有关更多信息,我建议:数据库索引如何工作?而且,索引如何提供帮助?


现在,假设我们想运行查询来查找名为’Abc’的所有员工的所有详细信息?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

没有索引会发生什么?

数据库软件从字面上必须查看Employee表中的每一行,以查看该行的Employee_Name是否为’Abc’。而且,因为我们希望每一行里面都有’Abc’这个名字,所以一旦我们找到一行名为’Abc’的行,我们就不能停止查找,因为可能有其他行的名称为Abc。因此,直到最后一行为止的每一行都必须被搜索 – 这意味着在这种情况下成千上万行将被数据库检查以查找名称为’Abc’的行。这就是所谓的全表扫描

数据库索引如何提高性能

具有索引的全部要点是通过基本上减少需要检查的表中的记录/行数来加速搜索查询。索引是一种数据结构(最常见的是B-树),用于存储表中特定列的值。

B树索引如何工作?

B树是索引中最流行的数据结构的原因是由于它们具有时间效率 – 因为查找,删除和插入都可以在对数时间内完成。而且,B-树更常用的另一个主要原因是因为可以对存储在B-树内的数据进行排序。RDBMS通常确定哪个数据结构实际用于索引。但是,在某些使用某些RDBMS的场景中,实际上可以指定在创建索引时希望数据库使用哪种数据结构。

哈希表索引如何工作?

使用哈希索引的原因是因为哈希表在查找值时非常高效。因此,如果使用散列索引,那么与字符串进行比较的查询可以非常快速地检索值。

例如,我们前面讨论的查询可以从Employee_Name列上创建的哈希索引中受益。散列索引的工作方式是列值将成为哈希表的键值,映射到该键值的实际值只是指向表中的行数据的指针。由于哈希表基本上是一个关联数组,因此典型的条目看起来像“Abc => 0x28939”,其中0x28939是对Abc存储在内存中的表行的引用。在哈希表索引中查找像“Abc”这样的值并取回对内存中行的引用显然要比扫描表找到Employee_Name列中值为“Abc”的所有行快得多。

哈希索引的缺点

哈希表不是有序的数据结构,并且有许多类型的查询哪些哈希索引甚至无法帮助。例如,假设你想找出所有40岁以下的员工。你怎么能用哈希表索引来做到这一点?那么,这是不可能的,因为散列表只适用于查找关键值对 – 这意味着查询检查是否相等

数据库索引究竟是什么? 因此,现在您知道数据库索引是在表中的列上创建的,并且索引将该值存储在该特定列中。但是,理解数据库索引不会将值存储在同一表的其他列中很重要。例如,如果我们在Employee_Name列上创建索引,这意味着Employee_Age和Employee_Address列值不会同时存储在索引中。如果我们只是将所有其他列存储在索引中,那么就像创建整个表的另一个副本一样 – 这会占用太多空间并且效率非常低。

数据库如何知道何时使用索引? 当运行“SELECT * FROM Employee WHERE Employee_Name =’Abc’”这样的查询时,数据库将检查被查询的列是否存在索引。假设Employee_Name列确实有索引创建,数据库将不得不决定使用索引来查找正在搜索的值是否合理 – 因为在某些情况下,使用数据库索引实际上效率较低,并且更有效地扫描整个表格。

拥有数据库索引的成本是多少?

它占用空间 – 桌子越大,指数越大。索引的另一个性能是,无论何时添加,删除或更新相应表中的行,都必须对索引执行相同的操作。请记住,索引需要包含与索引覆盖的表列中的任何内容相同的分钟数据。

一般来说,如果索引列中的数据将经常被查询,则只应在表上创建索引。

也可以看看

  1. 哪些列通常能够创建好的索引?
  2. 数据库索引如何工作

添加评论

友情链接:蝴蝶教程