数据库索引如何工作？

鉴于indexing是非常重要的，因为你的数据集的规模增加了，有人可以解释索引如何在database-agnostic层面上工作吗？

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

---

为什么需要？

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

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

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

什么是索引？

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

索引的缺点是这些索引需要额外的磁盘空间，因为索引使用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

注意 ：字符被用来代替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个块。

如果id字段是关键字段，那么对id字段进行线性搜索将需要平均N/2 = 500,000块访问来查找值。 但是由于id字段也被排序，所以可以进行二分搜索，要求平均log2 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 = 54个字节，并且使用缺省块大小B = 1,024字节的r = 5,000,000条记录。 索引的阻塞因子为每个磁盘块的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％，查询优化器将避免使用索引，从而有效地使索引浪费空间。

---

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

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

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

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

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

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

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

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

---

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

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

链接地址: http://www.djcxy.com/p/6695.html

上一篇: How does database indexing work?

下一篇: Computational complexity of a longest path algorithm witn a recursive method