什么是数据库索引

前言

数据库索引?什么是数据库索引?在维基百科中是这样写的:数据库索引是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。简单来说,数据库索引就像书籍的目录一样,可以提高查询的效率,接下来我们就一起仔细分析下数据库的索引是什么样的,以及MySQL数据库有哪些索引。

什么是数据库索引

B+树的结构和特性

众所周知,如果我们想要在一堆数据中查询一个数据,那么时间复杂度最低只需要O(logN),也就是使用二分查找,而二分查找的前置条件就是数据需要有序,而想要在一个数据流(不断地有输入的数据)中,我们联想一下十大排序,我们很轻松的可以得出,堆排序是最合适的,而堆排序的底层就是树形结构。

说了这么多,其实主要就是想说在数据流中查找一个数据最好的存储数据的数据结构就是树形结构

说到树形结构,我们可以很快想到:平衡排序树、红黑树、前缀树等等。那么哪一种树型结构最适合用在数据库的存储数据上呢?首先我们可以确定我们一定要选用平衡树,因为平衡树可以避免一个查询过多的落在最长的那个分支上,比如下图的6号结点。

什么是数据库索引

确定了平衡树的话,那我们用红黑树可不可以?我们首先思考下,数据库的数据都是存在硬盘上的,如果想要从硬盘上读取一个数据,我们需要哪些步骤?首先硬盘想要读取一个数据必须先要寻道,让磁盘的指针寻找到数据的位置,然后再将数据所在的数据块读取到内存中,然后才算是读到了数据。

如果采用红黑树的话,如果一个表有十万行数据,那么红黑树的层高就是17层(2^17 > 10万),那么如果我想查一个数据,那就需要寻道17次,进行17次io,那么这个时间成本要在毫秒级别了,显然是不可接受的。

那么红黑树不适合数据库存储,有没有其他的数据结构呢?当然有了,前辈们根据磁盘存储的这种特性,发明出一种新的数据结构叫做B+树专门用来作为数据库索引的数据结构。接下来我们就聊一聊B+树的结构和特性。

首先是说一下B+树的结构特点:

  1. B+树是一个平衡树
  2. B+树一个节点的大小等于硬盘上一个数据块的大小
  3. B+树一个结点可以有多个子结点
  4. B+树只有最底层的叶子结点存储数据
  5. B+树最底层的叶子结点是由双向循环链表构成

根据上面描述的结构特点,我们的B+树最后的结构如下图所示:

什么是数据库索引

接下来我们就来说说为什么B+树是这样子的。

  • B+树为什么要设计成平衡树?平衡树可以很好的避免前文提到的大量查询落在一个很长的树分支上,降低最坏情况下的时间复杂度。
  • B+树的结点大小为什么等于硬盘上数据库的大小?因为硬盘即使每次只读取一个字节的数据,也是将硬盘上的一块数据读入内存,所以将结点大小设计成硬盘快大小可以更好的利用硬盘空间,在一个结点中存储多个数据,这样也可以降低树的高度从而减少读取磁盘的次数,提高效率。
  • B+树为什么一个结点要有多个子结点?因为B+树一个结点含有多个值,多个值有多个区间,所以需要一个结点指向多个子节点。
  • B+树为什么只有最底层的叶子结点存储数据?因为数据一般是比较大的,如果在中间的结点中存储数据,可能一个节点只能有很少的叶子结点,这样反而增加了树的高度,增加了IO的次数,降低了查询的效率。
  • B+树最底层的结点为什么是由双向循环链表构成?因为最底层存储的是数据,我们在查询数据的时候很多时候都是查询一个范围,比如id>10的数据,底层是双向链表就可以大大优化这种范围查询的效率,因为我不需要一个个查询来判断这一个数据的id是不是大于10,我只需要找到第一个大于10的数据,然后返回这一行数据后面的所有数据即可,同样也是为了提高效率。

聚簇索引和非聚簇索引

聚簇索引和非聚簇索引其实说的是数据和索引的存储方式,聚簇索引和非聚簇索引的底层结构都是B+树。

聚簇索引是在数据库中将数据放在索引的B+树的叶子节点上,而非聚簇索引则是将指向数据的指针放在叶子节点上。这就造成了检索方式上的区别,通过聚簇索引,我们可以直接定位数据块的位置,所以聚簇索引具有唯一性,只能有一个聚簇索引,同时聚簇索引的索引和数据行在物理结构上是一致的,数据行按照一定顺序排序,并且自动维护这个顺序;非聚簇索引我们只能知道指针,我们在通过指针进行查找数据。

聚簇索引也带来一个坏处就是因为只能有一个聚簇索引,所以其他索引就只能在叶子结点存储聚簇索引的值,然后在通过值在聚簇索引中查找,从而找到数据的位置。

什么是数据库索引

联合索引

联合索引是将多个列联合起来作为一个索引,比如我们将A、B、C三个列创建一个联合索引,那么相当于创建了A、AB、ABC三个索引,所以联合索引在搜索的时候是最左匹配原则,也就是说,匹配上A,然后在匹配B,然后再匹配C。也是因为联合索引的这种机制,所以联合索引在一些特殊情况下会失效,比如:

  • 未使用最左匹配。
  • where语句后存在OR条件。因为联合索引的匹配规则是先匹配A然后再匹配B,所以一旦存在了OR,比如A = 1 or B = 2,这个条件在A != 1 && B == 2的情况下也是合法的,但是他没有匹配到A = 1,所以就无法使用联合索引。
  • like以%开头。like以%开头强调的是模糊前缀匹配,所以也没办法走联合索引。
  • where中索引列有运算
  • where中索引列使用了函数
  • 如果mysql觉得全表扫描更快

原创文章,作者:Rosmontics,如若转载,请注明出处:https://rosmontis.com/archives/185

(1)
上一篇 2022年5月7日
下一篇 2022年5月7日
alt

相关推荐

发表回复

登录后才能评论

评论列表(1条)

TG通知群
小程序
小程序
分享本页
返回顶部