索引是万能的吗?

首先要了解什么是索引(index)。数据库中的索引,就好比一本书的目录,它可以帮我们快速进行特定值的定位与查找,从而加快数据查询的效率。

索引就是帮助数据库管理系统搞笑获取数据的数据结构。

索引不是万能的,在有些情况下使用索引反而会让效率变低。

在数据表中的数据行数比较少的情况下,比如不到1000行,是不需要创建索引的。另外,当数据重复度大,比如高于10%的时候,也不需要对这个字段创建索引。

索引的种类有哪些

从功能逻辑上说,索引主要有4种,分别是普通索引、唯一索引、主键索引和全文索引。

普通索引是基础的索引,没有任何约束,主要用于提高查询效率。唯一索引就是在普通索引的基础上增加了数据唯一性的约束,在一张数据表里可以有多个唯一索引。主键索引在唯一索引的基础上增加了不为空的约束,也就是NOT NULL + UNIQUE,一张表里最多只有一个主键索引。全文索引用的不多,MySQL自带的全文索引只支持英文。我们通常可以采用专门的全文搜索引擎,比如ES。

其实前三种索引(普通索引,唯一索引,主键索引)都是一类索引,只不过对数据的约束性逐渐提升。在一张数据表中只能有一个主键索引,这是由主键索引的物理方式决定的,因为数据存储在文件中只能按照一种顺序进行存储。但可以有多个普通索引或多个唯一索引。

按照物理实现方式,索引可以分为2种:聚集索引和非聚集索引。我们也可以把非聚集索引称为二级索引或者辅助索引。

聚集索引

聚集索引可以按照主键来排序存储数据,这样在查找行的时候非常有效。举个例子,如果是一本汉语字典,我们想要查找“数”这个字,直接在书中找汉语拼音的位置即可,也就是拼音shu。这样找到了索引的位置,在他后面就是我们想要找的数据行。

非聚集索引

在数据库系统会有单独的存储空间存放非聚集索引,这些索引项是按照顺序存储的,但索引项指向的内容是随机存储的。也就是说系统会进行两次查找,第一次先找到索引,第二次找到索引对应的位置取出数据行。非聚集索引不会把索引指向的内容像聚集索引一样直接放到索引的后面,而是维护单独的索引表(只维护索引,不维护索引指向的数据),为数据的检索提供方便。还以汉语字典为例,如果想要查找“数”字,那么按照部首查找的方式,先找到“数”字的偏旁部首,然后这个目录会告诉我们“数字”存放在低多少页,我们再去指定的页码找到这个字。

聚集索引与非聚集索引的原理不同,在使用上也有一些区别:

  1. 聚集索引的叶子节点存储的就是我们的数据记录,非聚集索引的叶子节点存储的是数据位置。非聚集索引不会影响数据表的物理存储结构。
  2. 一个表只能有一个聚集索引,因为只能有一种排序存储的方式,但可以有多个非聚集索引,也就是多个索引目录提供数据检索,
  3. 使用聚集索引的时候,数据的查询效率高,但如果对数据进行插入,删除,更新等操作,效率会比非聚集索引低。

建议:

  1. 对WHERE子句的字段建立索引,可以大幅提升查询效率。
  2. 采用聚集索引进行数据查询,比使用非聚集索引查询效率略高。如果查询次数较多,还是尽量使用主键索引进行数据查询。

除了业务逻辑和物理实现方式,索引还可以按照字段个数进行划分,分成单一索引和联合索引。

索引列为一列时为单一索引;多个列组合在一起创建的索引叫做联合索引。

创建联合索引时,我们需要注意创建时的顺序问题,因为联合索引(x,y,z)和(z,y,x)在使用的时候效率可能会存在差别。

这里需要说明的是联合索引存在最左匹配原则,也就是按照最左优先的方式进行索引的匹配。比如刚才举例的 (x, y, z),如果查询条件是 WHERE x=1 AND y=2 AND z=3,就可以匹配上联合索引;如果查询条件是 WHERE y=2,就无法匹配上联合索引。

索引原理

数据库服务器的两种存储介质,分别为硬盘和内存。内存属于临时存储,容量有限,而当发生意外时会造成数据丢失;硬盘相当于永久存储介质,这也是为什么我们需要把数据保存到硬盘上。

虽然内存的读取速度很快,但我们还是需要将索引存放到硬盘上,这样的话,当我们在硬盘上进行查询时,也就产生了磁盘的I/O操作。相比于内存的存取来说,硬盘的I/O存取消耗的时间要高很多,所消耗的时间也就越大。如果我们能让索引的数据结构尽量减少硬盘的I/O操作,所消耗的时间也就越小。

二叉树的局限性

二分查找法是一种高效的数据检索方式,时间复杂度为O(log2n),是不是采用二叉树就适合作为索引的数据结构呢?

二叉搜索树

假设搜索插入的数值为key:

  1. 如果key大于根节点,则在右子树种进行查找;
  2. 如果key小于根节点,则在左子树中进行查找;
  3. 如果key等于根节点,也就是找到了这个节点,返回根节点即可。

例子,对数列(34,22,89,5,23,77,91)创造出来的二叉树如图:
image.png

但是存在特殊的情况,就是有时候二叉树的深度非常大。比如(5,22,23,34,77,89,91)二叉搜索树如图所示:
image.png

可以看出来第一个数的深度时3,也就是说最多只需要3次比较,就可以找到节点,而第二棵树的深度时7,最多需要7次比较才能找到节点。

第二棵树也属于二分查找树,但是性能已经退化成了一条链表,查找数据的时间复杂度编程了O(n)。为了解决这个问题,人们提出了平衡二叉搜索树(AVL树),它在二分搜索树的基础上增加了约束,每个节点的左子树和右子树的高度不能超过1,也就是左子树和右子树仍然为平衡二叉树。

常见的平衡二叉树有很多种,包括了平衡二叉树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来的自平衡二叉搜索树,当我们提到平衡二叉树时一般指的就是平衡二叉搜索树。事实上第一棵树就属于平衡二叉搜索树,搜索时间复杂度就是O(log2n)。

数据查询的时间主要依赖于磁盘I/O的次数,如果我们采用二叉树的形式,即使通过平衡二叉树进行了改进,树的深度也是O(log2n),当n比较大时,深度也是比较高的,比如:
image.png

每访问一次节点就需要进行一次磁盘 I/O 操作,对于上面的树来说,我们需要进行 5 次 I/O 操作。虽然平衡二叉树比较的效率高,但是树的深度也同样高,这就意味着磁盘 I/O 操作次数多,会影响整体数据查询的效率。

针对同样的数据,如果我们把二叉树改成了M叉树呢?当M=3时,同样的31个节点由三叉树进行存储:
image.png

你能看到此时树的高度降低了,当数据量 N 大的时候,以及树的分叉数 M 大的时候,M 叉树的高度会远小于二叉树的高度。

B树

如果使用二叉树作为索引的实现结构,会让树变的很高,增加硬盘的I/O次数,影响数据查询的时间。因此一个节点就不能只有2个子节点,而应该允许有M个子节点(M>2)。

B树的出现就是为了解决这个问题的,英文时Balance Tree,也就是平衡多路搜索树,他的高度远小于平衡二叉树的高度。

B树的结构如下图所示:

image.png

B树作为平衡的多路搜索树,他的每一个节点最多可以包括M个子节点,M称为B树的阶。同时你能看到,每个磁盘块种包括了关键字和子节点的指针。如果一个磁盘块种包括了x个关键字,那么指针树就是x+1。对于一个100阶的B树来说,如果由三层的话最多可以存储约100万的索引数据。对于大量的索引数据来说,采用B树的结构是非常合适的,因为树的高度要远小二叉树的高度。

然后我们来看下如何用 B 树进行查找。假设我们想要查找的关键字是 9,那么步骤可以分为以下几步:

  1. 我们与根节点的关键字 (17,35)进行比较,9 小于 17 那么得到指针 P1;
  2. 按照指针 P1 找到磁盘块 2,关键字为(8,12),因为 9 在 8 和 12 之间, 所以我们得到指针 P2;
  3. 按照指针 P2 找到磁盘块 6,关键字为(9,10),然后我们找到了关键字 9

你能看出来在 B 树的搜索过程中,我们比较的次数并不少,但如果把数据读取出来然后在内存中进行比较,这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作,消耗的时间比在内存中进行比较所需要的时间要多,是数据查找用时的重要因素,B 树相比于平衡二叉树来说磁盘 I/O 操作要少,在数据查询中比平衡二叉树效率要高。

B+树

B+树基于B树做出了改进,主流的DBMS都支持B+树的索引方式,比如MySQL。

与B树的差异有以下几点:

  1. k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数,而 B 树中,孩子数量 = 关键字数 +1。
    1. 非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大(或最小)。
    2. 非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都放在叶子节点中。而 B 树中,非叶子节点既保存索引,也保存数据记录。
    3. 所有关键字都在叶子节点出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

image.png

比如,我们想要查找关键字 16,B+ 树会自顶向下逐层进行查找:

  1. 与根节点的关键字 (1,18,35) 进行比较,16 在 1 和 18 之间,得到指针 P1(指向磁盘块 2)
  2. 找到磁盘块 2,关键字为(1,8,14),因为 16 大于 14,所以得到指针 P3(指向磁盘块 7)
  3. 找到磁盘块 7,关键字为(14,16,17),然后我们找到了关键字 16,所以可以找到关键字 16 所对应的数据。

整个过程一共进行了 3 次 I/O 操作,看起来 B+ 树和 B 树的查询过程差不多,但是 B+ 树和 B 树有个根本的差异在于,B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢?

首先,B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据,而在 B 树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况,有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。

其次,B+ 树的查询效率更高,这是因为通常 B+ 树比 B 树更矮胖(阶数更大,深度更低),查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小,B+ 树可以存储更多的节点关键字。

不仅是对单个关键字的查询上,在查询范围上,B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中,并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。

总结
磁盘的 I/O 操作次数对索引的使用效率至关重要。虽然传统的二叉树数据结构查找数据的效率高,但很容易增加磁盘 I/O 操作的次数,影响索引使用的效率。因此在构造索引的时候,我们更倾向于采用“矮胖”的数据结构。

B 树和 B+ 树都可以作为索引的数据结构,在 MySQL 中采用的是 B+ 树,B+ 树在查询性能上更稳定,在磁盘页大小相同的情况下,树的构造更加矮胖,所需要进行的磁盘 I/O 次数更少,更适合进行关键字的范围查询。