问题

鉴于索引是如此重要,因为您的数据集在大小上增加,有人可以解释索引在数据库不可知级别如何工作吗?

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



解决方法

为什么需要?

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

由于多个记录只能在一个字段上排序,因此我们可以声明,对未排序的字段进行搜索需要一个线性搜索,需要 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,以允许磁盘上的精确大小值. 此样本数据库包含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字段也被排序,因此可以进行二叉搜索,要求平均 100002 = 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 字节且使用默认块大小的 r = 5,000,000 记录的样本数据库 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 块访问,与需要的1,000,000次访问相比, em> firstName match in the non-indexed table.

应何时使用?

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

由于索引仅用于加速在记录中搜索匹配字段,因此,在执行插入或删除操作时,仅仅用于输出的索引字段将仅仅是浪费磁盘空间和处理时间,因此应该避免.还给出二分搜索的性质,数据的基数或唯一性是重要的.在基数为2的字段上建立索引会将数据拆分为一半,而基数为1,000的数据将返回大约1,000条记录.有了这么低的基数,有效性被降低到线性排序,如果基数小于记录数的30%,查询优化器将避免使用索引,有效地使索引浪费空间.




相关问题推荐