数据库索引笔记



一句话简单来说,索引的出现其实就是为了提高数据查询的效率,就像书的目录一样。一本500页的书,如果你想快速找到其中的某一个知识点,在不借助目录的情况下,那我估计你可得找一会儿。同样,对于数据库的表而言,索引其实就是它的“目录”。

几种索引的常见模型

实现索引的方式却有很多种,所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多,以下是三种常见、也比较简单的数据结构:

  • 哈希表
  • 有序数组
  • 搜索树

哈希表

哈希表是一种以 键-值(key-value)存储数据的结构,我们只要输入待查找的值(key),就可以找到其对应的值(Value)。哈希的思路很简单,把值放在数组里,用一个哈希函数把 key 换算成一个确定的位置,然后把 value 放在数组的这个位置。

而不可避免地,多个 key 值经过哈希函数的换算,会出现同一个值的情况。处理这种情况的一种方法是,拉出一个链表。当要找某个 Value 的时候先算出哈希再顺序遍历找到需要的值。

需要注意的是,不管是哈希还是后面的链表,存放值的时候都不是有序的,虽然这样增加数据的时候速度很快,但是如果要做区间查询速度会很慢,需要全部扫描一遍。因此,哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

顾名思义,是一种按顺序存放数据的数组结构。有序数组在等值查询和范围查询场景中的性能就都非常优秀

正因为是顺序的,等值查找的时候用二分法很快就能得到,这个时间复杂度是 O(log(N))。区间范围搜索则用二分法定位第一个值,然后向右遍历,直到超出范围则退出循环。如果仅仅看查询效率,有序数组就是最好的数据结构了。

但是,在需要更新数据的时候就麻烦了,为了保持有序,无序插入记录时就要挪动后面所有的记录,成本太高。所以,有序数组索引只适用于静态存储引擎,比如你要保存的是 2017 年某个城市的所有人口信息,这类不会再修改的数据。

二叉搜索树、N叉树

二叉搜索树是很经典的数据结构,它的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。如果要查询某个值,通过对比大小可以避免遍历所有的值。这个时间复杂度是 O(log(N)) 。

数据库索引笔记

但是有一个经典的问题,当数据是按特定顺序插入的时候,数据都会往其中一边一直插入(左小右大原则),几乎变成了链表,这时它的搜索性能已经是线性的了。

数据库索引笔记

于是乎为了维持 O(log(N)) 的查询复杂度,二叉搜索树就需要保持自己是平衡二叉树。不过其更新的时间复杂度也是 O(log(N)) 。

至此,二叉树是搜索效率最高的,但是实际上大多数的数据库存储却并不使用二叉树。其原因是,索引不止存在内存中,还要写到磁盘上,树的不同结点很可能不在磁盘的同一页中,所以还要考虑到磁盘的寻址加载次数。

既然树可以有二叉,也可以有多叉。多叉树就是每个节点有多个儿子,儿子之间的大小保证从左到右递增。同一层的节点多了,树的深度就不用那多大了,从而减少了磁盘寻址加载的次数。

假设一棵100万节点的平衡二叉树,树高20。一次查询可能需要访问20个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说,对于一个100万行的表,如果使用二叉树来存储,单独访问一个行可能需要20个10ms的时间,这个查询效率明显被拖慢了。

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

以 InnoDB 的一个整数字段索引为例,这个N差不多是1200。这棵树高是4的时候,就可以存1200的3次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个10亿行的表上一个整数字段的索引,查找一个值最多只需要访问3次磁盘。再有,其实树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

N叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中了。

B树

B树(B-Tree)是一种平衡多叉搜索树,B就是Balanced(平衡的)的意思。

和多叉树一样,B树的所有节点都可以存放数据,不过在多叉树的基础上通过重新组织节点,降低树的高度,从而减少IO读写次数来提升效率。

数据库索引笔记

B树的特点:

  • B树的叶子结点和非叶子节点都会存放数据或主键等,也叫做关键字,用于搜索对比。
  • 搜素性能等价于在全集内做一次二分查找。
  • 所有的叶子节点都在同一层。
  • 每个根节点至少2个子女。
  • 每个非根节点所包含关键字个数 j 满足:⌈m/2]-1 ≤ j ≤ m−1(m为树的阶)
  • 非根节点的所有节点(不包括叶子节点)的度数正好是关键字总数加1,子树个数 k :⌈m/2⌉ ≤ k ≤ m(m为树的阶)

B+树

B+树是B树基础上的一种变体,也是一种多路搜索树,主要区别特征有以下:

  • 数据都存在叶子结点上面,父节点上的是关键字索引,是子节点上最大或者最小的元素。
  • 每个叶子节点都有一个指针,指向下一个数据,形成一个有序链表。
  • 非叶子结点仅具有索引作用,当搜索时,B+树只可能在叶子节点命中被查询的数据,不能在非叶子节点命中。

数据库索引笔记

B+树中间节点没有Data数据,所以同样大小的磁盘页可以容纳更多的节点元素。所以数据量相同的情况下,B+树比B树更加“矮胖”,因此使用的IO查询次数更少,更适合文件系统。

B树和B+树的插入、删除过程

关于B树和B+树数据的插入、删除、页分裂、页合并等等知识点参考这位大佬的博文 ->
B树和B+树的插入、删除图文详解

再发展还有B*树,是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针。

不管是哈希、有序数组,再到N叉树、B树、B+树等,它们都是不断迭代、不断优化的产物或者解决方案。数据库技术发展到今天,跳表、LSM树等数据结构也被用于引擎设计中,这里就不再一一展开了。

在MySQL中,索引是在存储引擎层实现的,所以并没有统一的索引标准,即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引,其底层的实现也可能不同。以下用常用的InnoDB存储引擎为例,分析其索引模型,以后遇到问题时再举一反三,根据不同索引的模型分析问题、解决问题。

InnoDB 的索引模型

在InnoDB存储引擎中,每张表都有个主键。

  1. 如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索引。
  2. 如果没有则判断表中是否有非空的唯一索引(Unique NOT NULL),如果有,则该列即为主键。如果多个,取第一个。
  3. 如果不符合上述条件,InnoDB存储引擎自动创建一个6字节大小的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增,这个ROWID不像ORACLE的ROWID那样可引用,是隐含的)。

表都是根据这个主键顺序组织存放的,这种存储方式的表称为索引组织表(index organized table IOT)

数据库索引笔记

InnoDB默认索引结构使用 B+ 树作为索引模型(空间索引采用R树,此处不引申),数据记录本身被存于主索引(B+Tree)的叶子节点上。


参考博文

原创文章,作者:wdmbts,如若转载,请注明出处:https://blog.ytso.com/tech/database/275955.html

(0)
上一篇 2022年7月22日 03:26
下一篇 2022年7月22日 03:26

相关推荐

发表回复

登录后才能评论