乐趣区

关于索引:数据库索引总结

索引简介

索引是一种数据结构,索引的呈现是为了进步数据查问的效率。查问效率个别能够从等值查问和范畴查问两个方面进行评判。

索引的模型

哈希表

哈希表是一种以键 – 值(key-value)存储数据的构造,哈希的思路很简略,把值放在数组里,用一个哈希函数把 key 换算成一个确定的地位,而后把 value 放在数组的这个地位。

不同的 key 值通过哈希函数的换算,会呈现同一个值的状况。解决这种状况的一种办法是,拉出一个链表。

假如,当初保护着一个身份证信息和姓名的表,须要依据身份证号查找对应的名字,这时对应的哈希索引的示意图如下所示:

哈希表因为能够疾速的找到数据的地位,等值查问效率十分高,但哈希表中的值因为不保障程序,如果要查问某个范畴内的数据,就须要把整个哈希表中的值进行扫描判断。所以哈希表这种数据结构适宜比拟适宜等值查问,不适宜范畴查问的场景。

有序数组

有序数组保障了数组中的元素的值是依照肯定顺序存储的,还是下面的例子,假如身份证是不反复的,如下图:

如果要查 ID_card_n2 对应的名字,用 二分法 就能够疾速失去,这个工夫复杂度是 O(log(N))。

同时,这个索引构造反对范畴查问。要查身份证号 [ID_card_X, ID_card_Y] 区间的 User,能够先用 二分法 找到 ID_card_X(如果不存在 ID_card_X,就找到大于 ID_card_X 的第一个 User),而后向右遍历,直到查到第一个大于 ID_card_Y 的身份证号,退出循环。

如果仅仅看查问效率,有序数组就是比拟好的数据结构了。然而,在须要更新数据的时候就比拟麻烦了,往两头插入一个记录就必须得移动前面所有的记录,老本太高。所以,有序数组索引只实用于动态存储引擎。

二叉树

还是下面依据身份证号查名字的例子,如果咱们用二叉搜寻树来实现的话,示意图如下所示:

二叉搜寻树的特点是:父节点左子树所有结点的值小于父节点的值,右子树所有结点的值大于父节点的值。这样如果要查 ID_card_n2 的话,依照图中的搜寻程序就是依照 UserA -> UserC -> UserF -> User2 这个门路失去。这个工夫复杂度是 O(log(N))。

当然为了维持 O(log(N)) 的查问复杂度,你就须要放弃这棵树是均衡二叉树。为了做这个保障,更新的工夫复杂度也是 O(log(N))。

树能够有二叉,也能够有多叉。多叉树就是每个节点有多个儿子,儿子之间的大小保障从左到右递增,如图:

二叉树是搜寻效率最高的,然而实际上大多数的数据库存储却并不应用二叉树。其起因是,索引不止存在内存中,还要写到磁盘上。

如果数据库存储应用二叉树,那么树的高度就比拟大,设想一下一棵 100 万节点的均衡二叉树,树高 20。一次查问可能须要拜访 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块须要 10 ms 左右的寻址工夫。也就是说,对于一个 100 万行的表,如果应用二叉树来存储,独自拜访一个行可能须要 20 个 10 ms 的工夫。

为了让一个查问尽量少地读磁盘,就必须让查问过程拜访尽量少的数据块。那么,就不应该应用二叉树,而是要应用“N 叉”树来实现缩小树的高度。这里,“N 叉”树中的“N”取决于数据块的大小。

对于雷同个数的数据构建 N 叉树索引,N 叉树中的 N 越大,那树的高度就越小,那 N 叉树中的 N 是不是越大越好呢?到底多大才最合适呢?

不论是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是 4KB,这个值能够通过 getconfig PAGE_SIZE 命令查看)来读取的,一次会读一页的数据。如果要读取的数据量超过一页的大小,就会触发屡次 IO 操作。所以,咱们在抉择 N 大小的时候,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只须要一次磁盘 IO 操作。

N 叉树因为在读写上的性能长处,以及适配磁盘的拜访模式,曾经被广泛应用在数据库引擎中了。

InnoDB 的索引

索引模型

InnoDB 应用了 B+ 树索引模型,数据都是存储在 B+ 树中。每一个索引在 InnoDB 外面对应一棵 B+ 树。在 B + 树中,叶子节点通过一个有序的双向链表串起来。

假如,咱们有一个主键列为 ID 的表,表中有字段 k,并且在 k 上有索引,表中 R1~R5 的 (ID,k) 值别离为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵 B+ 树的示例示意图如下:

依据叶子节点的内容,索引类型分为主键索引和非主键索引:
1、主键索引的叶子节点存储的是 Page,Page 中是一个有序数组,通过二分法定位到对应的数据行。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。
2、非主键索引的叶子节点内容是 主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

主键索引和一般索引查问的区别:
如果语句是 select * from T where ID=500,即主键查问形式,则只须要搜寻 ID 这棵 B+ 树;
如果语句是 select * from T where k=5,即一般索引查问形式,则须要先搜寻 k 索引树,失去 ID 的值为 500,再到 ID 索引树搜寻一次。这个过程称为回表。

所以,基于非主键索引的查问须要多扫描一棵索引树。因而,在利用中应该尽量应用主键查问。

索引的类型

Normal:示意一般索引
Unique:示意惟一的,不容许反复的索引,如果该字段信息保障不会反复例如身份证号用作索引时,可设置为 unique
Full Text: 示意全文搜寻的索引。FULLTEXT 用于搜寻很长一篇文章的时候,成果比拟好

索引的保护

B+ 树为了保护索引有序性,在插入新值的时候须要做必要的保护。以下面这个图为例,如果插入新的行 ID 值为 700,则只须要在 R5 的记录前面插入一个新记录。

如果新插入的 ID 值为 400,就绝对麻烦了,须要逻辑上移动前面的数据,空出地位。而更糟的状况是,如果 R5 所在的数据页 P1 曾经满了,依据 B+ 树的算法,这时候须要申请一个新的数据 Pn,而后 P1 上须要移动局部数据到 Pn。本来在 P1 上的数据当初散布在 P1 和 Pn 两个数据页上了,这个过程称为页决裂。在这种状况下,性能天然会受影响。

除了性能外,页决裂操作还影响数据页的利用率。本来放在一个页的数据,当初分到两个页中,整体空间利用率升高大概 50%。

有决裂就有合并。当相邻两个页因为删除了数据,利用率很低之后,会将数据页做合并。合并的过程,能够认为是决裂过程的逆过程

自增主键

自增主键的插入数据模式,正合乎了咱们后面提到的递增插入的场景。每次插入一条新记录,都是追加操作,都不波及到移动其余记录,也不会触发叶子节点的决裂。而有业务逻辑的字段做主键,则往往不容易保障有序插入,这样写数据老本绝对较高。

除了思考性能外,咱们还能够从存储空间的角度来看。假如你的表中的确有一个惟一字段,比方字符串类型的身份证号,那应该用身份证号做主键,还是用自增字段做主键呢?

因为每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键,那么每个二级索引的叶子节点占用约 20 个字节,而如果用整型做主键,则只有 4 个字节,如果是长整型(bigint)则是 8 个字节。

显然,主键长度越小,一般索引的叶子节点就越小,一般索引占用的空间也就越小。所以,从性能和存储空间方面考量,自增主键往往是更正当的抉择。

索引的重建

索引可能因为删除,或者页决裂等起因,导致数据页有空洞,重建索引的过程会创立一个新的索引,把数据按程序插入,这样页面的利用率最高,也就是索引更紧凑、更省空间。

在非聚簇索引上应用索引重建,能够达到省空间的目标。比方:

alter table T drop index k;
alter table T add index(k);

然而,重建主键索引的过程须要留神。不论是删除主键还是创立主键,都会将整个表重建。所以其余保护好的索引就白保护了。主键索引的重建,能够用这个语句代替:

alter table T engine=InnoDB;
退出移动版