数据库索引如何工作?

Xenph Yan 2335 sql database indexing performance database-indexes

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

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

Xenph Yan.. 3426

为什么需要?

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

由于许多记录只能在一个字段上排序,我们可以声明搜索未排序的字段需要线性搜索,这需要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字节,并使用使用默认块大小B = 1,024字节的MyISAM引擎将它们存储在表中.表的阻塞因子是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字段上的索引的模式概述如下;

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每个磁盘块的记录.保存索引所需的块总数是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%,查询优化器将避免使用索引,从而有效地使索引浪费空间.

  • 我认为在这个答案中有一些拼写错误,例如,在句子中:"与非索引表所需的277,778个块访问相差甚远." 作者不是指1,000,000次访问块?277,778是索引本身所需的块数.似乎还有其他一些不准确之处:( (30认同)
  • 二进制搜索可以在数据唯一时完成,对不对?虽然你提到最小基数很重要,但算法不是简单的二进制搜索,这种近似(~log2 n)会如何影响处理时间? (7认同)
  • @AbhishekShivkumar:很棒的问题!我认为索引表将包含与数据表中一样多的行.并且因为这个字段只有2个值(布尔值为true/false)并且说你想要一个值为true的记录,那么你只能在第一次传递中将结果集减半,在第二次传递中所有记录的值都为真,所以有没有区分的基础,现在你必须以线性方式搜索数据表 - 因此他说在决定索引列时应该考虑基数.在这种情况下,在这样的列上索引是没有价值的.希望我是对的:) (7认同)
  • 不应该在平均情况下块访问的数量是"(N + 1)/ 2".如果我们总结所有可能情况的块访问次数,并将其除以个案数,那么我们得到'N*(N + 1)/(2*n)`,它是`(N + 1) )/ 2`. (6认同)
  • @jcm他在"什么是索引部分"中解释了它 - "索引是一种对多个字段上的多个记录进行排序的方法.在表中的字段上创建索引会创建另一个保存字段值的数据结构,以及指针然后对该索引结构进行排序,允许对其进行二进制搜索." (4认同)
  • 仅供参考,在b树查询中不使用二进制搜索。当索引不适合内存时,性能将很糟糕。“ b树索引”的原因是要快速,即使不是所有索引都适合可用内存。这是关于“扇出”键以找到数据的位置。二叉树的“扇出”数为2。“ b树”的扇出数“可以大于10”或更大-取决于密钥大小和“页面大小”。 (2认同)

Der U.. 234

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

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

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

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

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

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

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

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

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

147.3k.. 232

经典案例"书中索引"

考虑1000页的"书",除以100个部分,每个部分有X页.

简单,对吧?

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

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

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

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

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

  • 非常好比喻!好笑,我没有在书籍索引和数据库索引之间建立联系 (11认同)
  • “但是在开始时有一个索引页,您就在那里。” “你在那里”是什么意思? (2认同)

hcarreras.. 220

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

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

  • 这个答案的+1倍,因为我在试图找到一个简单的解释基本上是什么索引时发现了这个列表. (23认同)

Somnath Mulu.. 144

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

  • @mustaccio:所以默认情况下`create index`不包括其他列以及它应该包含的原因.`如果我们只是将所有其他列存储在索引中,那么就像创建整个表的另一个副本一样,这将占用太多空间并且效率非常低.这是索引的更通用版本.`CREATE INDEX ... INCLUDE`是考虑其他专栏的新版本.我解释的帖子正在考虑更广义的版本.如果我们考虑所有数据库,索引如何工作将成为一本书?不是吗?你认为答案是值得的吗? (8认同)
  • "数据库索引不会将值存储在其他列中" - 不是这样. (3认同)
  • @To Downvoters:您能解释一下哪里出了问题,以便我改善吗? (2认同)

小智.. 81

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

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

例如,我们有一个名为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"开头的名称将在索引中彼此相邻!


Raza.. 32

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

  • 这是评论,而不是答案. (3认同)
  • 由于它是一般性的注释,因此它更加可见,因此更有用。应该将此答案添加到哪个答案中? (3认同)

Alf Moh.. 31

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

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


归档时间:

查看次数:

815735 次

最近记录:

9 月,1 周 前