题 数据库索引如何工作?


鉴于索引在数据集大小增加时非常重要,有人可以解释索引在数据库无关的级别上的工作原理吗?

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


1878
2017-08-04 10:07


起源


你可以查一下 - 数据库索引如何工作? - Aniket Thakur


答案:


为什么需要?

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

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

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

什么是索引?

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

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

它是如何工作的?

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

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

注意:char用于代替varchar以允许磁盘值的准确大小。 此示例数据库包含五百万行并且未编入索引。现在将分析几个查询的性能。这些是使用的查询 ID (一个排序的关键字段)和一个使用 名字 (非键未分类字段)。

例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 块。

id字段的线性搜索需要平均值 N/2 = 500,000 块访问以查找值,假设id字段是关键字段。但由于id字段也被排序,因此可以进行二进制搜索,需要平均值 log2 1000000 = 19.93 = 20 阻止访问。我们可以立即看到这是一个巨大的进步。

现在 名字 字段既不是排序字段也不是键字段,因此二进制搜索是不可能的,值也不是唯一的,因此表格将需要搜索到结尾的确切 N = 1,000,000 阻止访问。正是这种情况,索引旨在纠正。

鉴于索引记录仅包含索引字段和指向原始记录的指针,因此它将比它指向的多字段记录小。因此索引本身比原始表需要更少的磁盘块,因此需要更少的块访问来迭代。关于索引的模式 名字 领域概述如下;

字段名称数据类型磁盘上的大小
firstName字符(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 块。

现在搜索使用了 名字 字段可以利用索引来提高性能。这允许以平均值的二进制搜索索引 log2 277778 = 18.08 = 19 阻止访问。要查找实际记录的地址,需要进一步访问块来读取,将总数记录到 19 + 1 = 20 阻止访问,与查找a所需的1,000,000个块访问相差甚远 名字 在非索引表中匹配。

什么时候应该使用?

鉴于创建索引需要额外的磁盘空间(上例中额外增加277,778个块,增加约28%),并且太多索引可能导致文件系统大小限制引起的问题,必须仔细考虑选择正确的要索引的字段。

由于索引仅用于加速在记录中搜索匹配字段,因此,仅用于输出的索引字段仅仅是在执行插入或删除操作时浪费磁盘空间和处理时间,因此应该避免。同样考虑到二进制搜索的性质,数据的基数或唯一性很重要。对基数为2的字段进行索引会将数据分成两半,而基数为1,000则会返回大约1,000条记录。如此低的基数,有效性会降低到线性排序,如果基数小于记录数的30%,查询优化器将避免使用索引,从而有效地使索引浪费空间。


2852
2017-08-04 10:41



二进制搜索可以在数据唯一时完成,对不对?虽然您提到最小基数很重要,但算法不是简单的二进制搜索,这种近似(~log2 n)会如何影响处理时间? - shampoo
@AbhishekShivkumar:很棒的问题!我认为索引表将包含与数据表中一样多的行。并且因为这个字段只有2个值(布尔值为true / false)并且你想要一个值为true的记录,那么你只能在第一次传递中将结果集减半,在第二次传递中所有记录的值都为真,所以有没有区分的基础,现在你必须以线性方式搜索数据表 - 因此他说在决定索引列时应该考虑基数。在这种情况下,在这样的列上索引是没有价值的。希望我是对的:) - Saurabh Patil
不应该是平均情况下的块访问次数 (N+1)/2。如果我们将所有可能情况的块访问次数相加,并将其除以个案数,那么我们就可以了 N*(N+1)/(2*n) 这是出来的 (N+1)/2。 - ajay
我认为在这个答案中有一些拼写错误,例如,在句子中:“与非索引表所需的277,778个块访问相差甚远。”作者不是指1,000,000次访问块? 277,778是索引本身所需的块数。似乎还有其他一些不准确之处:( - jcm
@jcm他在“什么是索引部分”中解释了它 - “索引是一种对多个字段上的多个记录进行排序的方法。在表中的字段上创建索引会创建另一个保存字段值的数据结构,以及指针然后对该索引结构进行排序,允许对其进行二进制搜索。“ - grinch


我第一次看到它对我很有帮助。谢谢。

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

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

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

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

例如: - 如果您有很多可以与之对应的写入,但只能在工作时间之外每晚阅读一次以进行报告。

此外,聚簇索引和非聚簇索引之间的区别是非常重要的。

帮助过我:- 群集和非群集索引实际上意味着什么?


176
2018-04-30 14:31



我认为,这些索引问题可以通过维护两个不同的数据库来解决,就像Master和Slave一样。 Master可用于插入或更新记录。没有索引。并且奴隶可以用正确的索引读取??? - bharatesh
不,错,抱歉。不仅要更新表的内容,还要更新索引结构和内容(b-tree,nodes)。你的主人和奴隶的概念在这里毫无意义。但是,可行的是复制或镜像到第二个数据库,在该数据库上进行分析以使该工作负载远离第一个数据库。第二个数据库将保存数据副本 和 该数据的索引。 - Der U
雅...!尝试阅读我的评论并正确理解。我也说过同样的,我把master和slave(无论如何)称为“对第二个数据库进行分析或镜像,在该数据库上进行分析以将该工作负载从第一个数据库中移除。第二个数据库将保存数据和索引的副本那个数据“ - bharatesh
第二个数据库 - 完成镜像或复制,从属 - 将像第一个那样经历所有数据操作。对于每个dml操作,第二个数据库上的索引将遇到“这些索引问题”。我没有看到这方面的好处,无论何时需要索引并为快速分析而构建它们都需要保持最新。 - Der U


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

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


131
2018-02-20 14:40



这个答案的+1倍,因为我在试图找到一个简单的解释时找到了这个列表。 - Josh Burson


现在,假设我们要运行查询以查找名为“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. 数据库索引如何工作

94
2017-08-13 18:36



“数据库索引不会将值存储在其他列中” - 不是这样。 - mustaccio
@mustaccio:Index仅存储带有索引列的行的引用(据我所知)。我可能错了。您是否有任何参考说明索引存储其他列值? - Somnath Muluk
@To Downvoters:你能解释一下是什么问题,以便我能改进吗? - Somnath Muluk
检查示例SQL Server群集索引或DB2 CREATE INDEX ... INCLUDE 条款。在我看来,你的答案中有太多的概括。 - mustaccio
@mustaccio:默认情况下 create index 不包括其他列及其原因。 If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table, which would take up way too much space and would be very inefficient.。这是索引的更通用版本。 CREATE INDEX ... INCLUDE 是考虑其他专栏的新版本。我解释的帖子正在考虑更广义的版本。如果我们考虑所有数据库,索引如何工作将成为一本书?不是吗?你认为答案是值得的吗? - Somnath Muluk


经典的例子 “书中索引”

考虑1000页的“书”,除以100个部分,每个部分有X页。

简单,对吧?

现在,如果没有索引页面,要查找以字母“S”开头的特定部分,除了扫描整本书之外别无其他选择。即:1000页

但是在开头有一个索引页面,你就在那里。更重要的是,要阅读任何重要的特定部分,您只需要一次又一次地查看索引页面。找到匹配的索引后,您可以跳过其他部分有效地跳转到该部分。

但是,除了1000页之外,你还需要另外~10页来显示索引页面,所以总共1010页。

因此,索引是一个单独的部分,它以排序顺序存储索引列+指向索引行的指针的值,以便进行有效的查找。

学校的事情很简单,不是吗? :P


86
2018-04-23 14:43



非常好比喻!好笑,我没有在书籍索引和数据库索引之间建立联系 - Yolo Voe
快速理解的好解释:D - ndh103


简单描述!!!!!!!!!!

索引只是一个数据结构,它存储表中特定列的值。在表的列上创建索引。

例如,我们有一个名为User的数据库表,其中有三列 - Name,Age和Address。假设User表有数千行。

现在,假设我们要运行查询以查找名为“John”的任何用户的所有详细信息。 如果我们运行以下查询。

SELECT * FROM User 
WHERE Name = 'John'

数据库软件实际上必须查看User表中的每一行,以查看该行的Name是否为'John'。这将需要很长时间。
这是索引帮助我们“索引用于通过基本上减少需要检查的表中的记录/行数来加速搜索查询”的地方。
如何创建索引

CREATE INDEX name_index
ON User (Name)

索引由一个表中的列值(例如:John)组成,并且这些值存储在数据结构中。
所以现在数据库将使用索引来查找名为John的员工,因为索引可能会按用户名的字母顺序排序。并且,因为它是有序的,这意味着搜索名称要快得多,因为所有以“J”开头的名称将在索引中彼此相邻!


47
2017-08-02 01:30





只是一个快速的建议..因为索引会花费额外的写入和存储空间,所以如果您的应用程序需要更多的插入/更新操作,您可能希望使用没有索引的表,但如果它需要更多的数据检索操作,您应该去索引表。


21
2018-01-14 06:44



这是评论,而不是答案。 - RonJohn


只需将数据库索引视为一本书的索引。  如果您有一本关于狗的书,并且您想要找到关于德国牧羊犬的信息,您当然可以翻阅书中的所有页面并找到您要找的内容,但这当然是耗时而且不是很快速。另一种选择是,您可以直接进入本书的“索引”部分,然后使用您正在查找的实体的名称(在本例中为德国牧羊犬)查找您要查找的内容,并查看页码快速找到你要找的东西。在数据库中,页码被称为指针,它将数据库定向到实体所在磁盘上的地址。使用相同的德国牧羊犬类比,我们可以有这样的东西(“德国牧羊犬”,0x77129),其中0x77129是存储德国牧羊犬的行数据的磁盘上的地址。

简而言之,索引是一种数据结构,它存储表中特定列的值,以加快查询搜索速度。


16
2017-12-21 17:16