sql - 数据库索引如何工作？

Question

鉴于索引随着数据集大小的增加而变得如此重要，有人可以解释索引如何在与数据库无关的级别上工作吗？

有关对字段进行索引的查询的信息，请查看如何索引数据库列。

Answer 1

为什么需要它？

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

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

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

什么是索引？

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

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

它是如何工作的？

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

字段名称 数据类型 磁盘大小
id (主键) 无符号 INT 4 字节
名字 Char(50) 50 字节
姓氏 Char(50) 50 字节
电子邮件地址 Char(100) 100 字节

注意：使用 char 代替 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,000鉴于 id 字段是关键字段，对 id 字段进行线性搜索需要平均块访问才能找到值。但由于 id 字段也已排序，因此可以进行二进制搜索，需要平均log2 1000000 = 19.93 = 20块访问。立即我们可以看到这是一个巨大的改进。

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

鉴于索引记录仅包含索引字段和指向原始记录的指针，因此按道理它会小于它所指向的多字段记录。所以索引本身比原始表需要更少的磁盘块，因此需要更少的块访问来迭代。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块访问对索引进行二进制搜索。要找到实际记录的地址，这需要进一步的块访问才能读取，从而带来块访问的总数，这与在非索引表中查找firstName19 + 1 = 20匹配所需的 1,000,000 次块访问相去甚远。

什么时候应该使用它？

鉴于创建索引需要额外的磁盘空间（从上面的示例中额外增加了 277,778 个块，增加了约 28%），并且索引过多会导致文件系统大小限制引起的问题，因此必须仔细考虑选择正确的要索引的字段。

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

Answer 2

经典示例“书籍索引”

考虑一本 1000 页的“书”，除以 10 个章节，每个章节有 100 页。

很简单吧？

现在，假设您要查找包含单词“ Alchemist ”的特定章节。如果没有索引页，除了浏览整本书/章节之外，您别无选择。即：1000 页。

这个类比在数据库世界中被称为“全表扫描” 。

但是有了索引页面，您就知道该去哪里了！而且，要查找任何重要的特定章节，您只需要一次又一次地查看索引页面。找到匹配索引后，您可以通过跳过其余部分有效地跳到该章节。

但是，除了实际的 1000 页之外，您还需要大约 10 页来显示索引，因此总共需要 1010 页。

因此，索引是一个单独的部分，它按排序顺序存储索引列的值 + 指向索引行的指针，以实现高效查找。

学校里的事情很简单，不是吗？:P

Answer 3

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

Answer 4

第一次读到这篇文章对我很有帮助。谢谢你。

从那时起，我对创建索引的缺点有了一些了解：如果你用一个索引写入一个表（UPDATE或INSERT），你实际上在文件系统中有两个写操作。一个用于表数据，另一个用于索引数据（以及对它的重新排序（以及 - 如果聚集 - 对表数据进行重新排序））。如果表和索引位于同一个硬盘上，这将花费更多时间。因此，没有索引（堆）的表将允许更快的写入操作。（如果你有两个索引，你最终会得到三个写操作，依此类推）

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

索引的另一个问题是随着数据的插入，它们会随着时间的推移而产生碎片。REORGANIZE有帮助，您必须编写例程才能完成。

在某些情况下，堆比带有索引的表更有帮助，

例如：- 如果您有很多相互竞争的写入，但在工作时间之外只有一个夜间阅读用于报告。

此外，聚集索引和非聚集索引之间的区别非常重要。

帮助我：-聚集索引和非聚集索引实际上是什么意思？

Answer 5

现在，假设我们要运行一个查询来查找任何名为“Abc”的员工的所有详细信息？

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

没有索引会怎样？

数据库软件实际上必须查看 Employee 表中的每一行，以查看该行的 Employee_Name 是否为“Abc”。而且，因为我们希望其中的每一行都带有名称“Abc”，所以一旦我们找到一个名称为“Abc”的行，我们就不能停止查找，因为可能还有其他行名称为Abc。因此，必须搜索直到最后一行的每一行——这意味着在这种情况下，数据库必须检查数千行才能找到名称为“Abc”的行。这就是所谓的全表扫描

数据库索引如何帮助提高性能

拥有索引的全部意义在于通过减少表中需要检查的记录/行数来加速搜索查询。索引是一种数据结构（最常见的是 B 树），用于存储表中特定列的值。

B树索引如何工作？

B-树是最流行的索引数据结构的原因是因为它们具有时间效率——因为查找、删除和插入都可以在对数时间内完成。而且，B-tree 更常用的另一个主要原因是因为存储在 B-tree 中的数据可以排序。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. 数据库索引如何工作

Answer 6

简单说明！

索引只不过是一种数据结构，用于存储表中特定列的值。索引是在表的列上创建的。

示例：我们有一个名为的数据库表，其中User包含三列 –Name和。假设该表有数千行。AgeAddressUser

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

SELECT * FROM User 
WHERE Name = 'John'

数据库软件实际上必须查看表中的每一行，User以查看Name该行是否为“John”。这将需要很长时间。

这index对我们有帮助：索引用于通过减少表中需要检查的记录/行数来加速搜索查询。

如何创建索引：

CREATE INDEX name_index
ON User (Name)

Anindex由一个表中的列值（例如：John）组成，这些值存储在数据结构中。

因此，现在数据库将使用索引来查找名为 John 的员工，因为该索引可能会按用户名称的字母顺序排序。而且，因为它是排序的，这意味着搜索名称要快得多，因为所有以“J”开头的名称将在索引中彼此相邻！

Answer 7

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

Answer 8

只需将数据库索引视为一本书的索引。

如果您有一本关于狗的书，并且想查找有关德国牧羊犬的信息，您当然可以翻阅这本书的所有页面并找到您要查找的内容-但这当然很耗时，而且不会非常快。

另一种选择是，您可以转到本书的索引部分，然后使用您正在查找的实体的名称（在本例中为德国牧羊犬）并查看页码来查找您要查找的内容快速找到您要查找的内容。

在数据库中，页码被称为一个指针，它将数据库指向实体所在的磁盘上的地址。使用相同的德国牧羊犬类比，我们可以有这样的东西（“德国牧羊犬”，0x77129），其中0x77129是存储德国牧羊犬行数据的磁盘上的地址。

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