sql - 数据库索引设计 - 数据库索引面试




数据库索引如何工作? (6)

简单说明!

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

示例:我们有一个名为User的数据库表,该表具有三列NameAgeAddress 。 假定User表具有数千行。

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

SELECT * FROM User 
WHERE Name = 'John'

数据库软件实际上必须查看User表中的每一行,以查看该行的Name是否为'John'。 这将花费很长时间。

这是index帮助我们的地方: 索引用于通过实质上减少需要检查的表中的记录/行数来加速搜索查询

如何创建索引:

CREATE INDEX name_index
ON User (Name)

index一个表中列值(例如:John)组成 ,这些值存储在数据结构中

因此,现在数据库将使用索引查找名为John的员工,因为该索引可能会按用户名的字母顺序进行排序。 而且,由于它是经过排序的,这意味着搜索名称的速度要快得多,因为所有以“ J”开头的名称都将在索引中紧挨着!

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

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


为什么需要它?

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

由于许多记录只能在一个字段上排序,因此我们可以说,在未排序的字段上进行搜索需要进行线性搜索,该搜索需要进行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

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

示例1- 排序与未排序字段

给定我们的样本数据库r = 5,000,000个固定大小的记录,记录长度为R = 204字节,并且使用MyISAM引擎将它们存储在表中,该引擎使用默认的块大小B = 1,024字节。 该表的阻塞因子为bfr = (B/R) = 1024/204 = 5每个磁盘块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 = 5,000,000条记录的示例数据库,索引记录长度为R = 54字节,并使用默认块大小B = 1,024字节。 索引的阻塞因子为bfr = (B/R) = 1024/54 = 18每个磁盘块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%,查询优化器将避免使用索引,有效地使索引浪费空间。


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

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

另一种选择是,您可以转到书的“索引”部分,然后使用要查找的实体的名称(在本例中为“德国牧羊犬”)找到所需的内容,并查看要查找的页码。快速找到您想要的东西。

在数据库中,页码称为指针,该指针将数据库定向到实体所在磁盘上的地址。 使用相同的德国牧羊犬类比,我们可能会有类似的内容(“德国牧羊犬”,0x77129),其中0x77129是磁盘上存储德国牧羊犬行数据的地址。

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


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

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


经典示例“书籍索引”

考虑一本1000页的“书”,该书被100个部分划分,每个部分有X页。

简单吧?

现在,没有索引页,要查找以字母“ S”开头的特定部分,除了浏览整本书,别无选择。 即:1000页

但是在开始时有一个索引页,您就在那里。 而且,要阅读重要的任何特定部分,您只需一次又一次地浏览索引页面。 找到匹配的索引后,您可以通过跳过其他部分来有效地跳到该部分。

但是,除了1000页之外,您还需要约10页才能显示索引页,因此总共需要1010页。

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

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





database-indexes