本文请前往PC端浏览。

论文周,写论文,你还在用word吗?

这次分享的主角是Typora的一个主题:Typora-LaTex-Theme。使用它,结合作者给我们提供的论文模板,我们可以快速地创作出一片论文,而无需关注各种格式、字体、字号的设定。

食用方式也很简单,在release里面下载对应操作系统的版本(各版本应该差不多,大小都一样……),然后将里面的两个CSS文件放到Typora主题文件夹里面,最后安装对应的字体即可,所有字体文件都可以在作者的另外一个仓库里面找到:

使用这个主题赶的一篇论文如下,写论文的全过程都感觉很舒服(虽然写论文本身让我很不舒服),没有Word那种设置各级标题、设置字体等需要在菜单栏点来点去的问题。用Typora把论文导出HTML后嵌入到这篇文章里面,读者可以感受一下这个主题。

请无视论文内容。此外,因为主题的样式表和博客一些样式重名了,所以最终样式就随博客了,比如各级标题。


论文

查找算法与数据结构在数据库中的应用

 

Sato
门头沟学院  计算机科学与技术
摘 要
数据库是为数据的高效存取而服务的,我们对数据库最频繁的操作就是查找。本文通过层层递进的方式说明各查找算法与相关数据结构的原理,包括二分查找、索引查找和排序二叉树,并分析它们在数据库中应用的优点与不足。最后进一步讲解B树与B+树,分析它们能在当今的数据库管理系统中广泛应用的原因。通过数据库索引这个例子,希望能加深读者对数据结构与算法在计算机科学中广泛应用的感受,提高学习数据结构与算法的兴趣。

关键词
数据库索引;二分查找;索引查找;排序二叉树;B树;B+树

 

数据库索引

数据库最常用的操作就是查询,一条查询语句的基本格式如下:

image-20220612101128338

这条语句背后的运行机制是根据WHERE后面的条件从数据表中取出相应数据。数据库中存储的数据一般是海量的,它按照一定的顺序存储在磁盘中。如果我们每查询一个数据都一条一条地从头到尾遍历是很耗时的。

如何高效地查询到需要的数据是DBMS开发者应该思考的问题。实际上,我们可以使用索引来加速数据库的查询。

索引是帮助MySQL高效获取数据的数据结构,索引对于良好的性能非常关键,尤其是当表中的数据量越来越大时,索引对于性能的影响愈发重要。索引优化应该是对查询性能优化最有效的手段了,它能够轻易将查询性能提高好几个数量级。[1]

如果我们将id设置为索引:

image-20220612100750288

接下来再使用SQL语句进行查找,数据库首先会找到索引,然后根据索引去寻访数据所在的位置。实际上,使用索引是一种典型的以空间换时间的做法,如何定义索引的数据结构,使用何种方法快速地找到索引,就是接下来需要探讨的问题。


 

索引查找的优化

要寻找最适合索引的数据结构,我们先从最熟悉的查找方式入手,层层深入进行探索。

 

线性表与二分查找

二分查找的原理

说起按值查位置的查找,我们最先想到的应该就是二分查找了。它在有序线性表的基础上,通过二分的方式,每次折半地进行查找,因此也称为折半查找。

image-20220611204927734

图1 二分查找

假设我们需要从图1的有序数组中查询到9这个元素。搜索过程从数组的中间元素开始:

  1. 如果中间元素正好是要查找的元素,则搜索过程结束。
  2. 如果需要查找的元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
  3. 当左指针和右指针重合时,它们指向的元素就是待查找的元素。
  4. 如果某一步左指针和右指针交错,则代表找不到。

按照这个步骤,中间指针经过的元素应该是:39

C++代码如下:

image-20220612100819642

二分查找的性能分析

由于每次折半,二分查找的时间复杂度为O(n),查找的性能是比较好的。

但是要保持这样的查找性能的代价是需要维护线性表的有序性,而对数组进行排序是比较耗时的。

另一方面,数据库中的操作除了查询外,还有大量的增删改。数组每次进行这样的操作都需要移动大量的元素,对于数据库这样的系统显然是不合理的。

还有什么数据结构能够高效地进行查找,同时插入和删除也比较方便呢?

 

哈希表与索引查找

索引查找的原理

索引查找使用的数据结构是哈希表,也成为散列表。它使用哈希函数将一个比较大的域空间映射到一个比较小的域空间。

常用的哈希函数就是对当前的值取模,除数一般是选取的一个大素数。我们可以将哈希函数看成一个加工的机器,它的输出就是哈希表中的地址。

 

image-20220611211059940

图2 哈希表

使用哈希函数,我们可以直接获得索引在哈希表中的位置。但是,可能会有多个键对应同一哈希表地址的情况,这时就需要解决冲突。

图2给出了解决冲突的一种方法,称为"拉链法",此外,还有"线性探测法"等。

索引查找的性能分析

索引位置的冲突在一定程度上会降低查询的效率。但是,如果哈希函数选得比较好的话,我们还是能保证查询时间复杂度在(O(1),O(2))之间的。

现在查询的效率有了质的飞跃,而且对于SELECT * FROM tableName WHERE id=1;这样的查询似乎已经足够了。

但是,如果是基于范围的查询,索引查找就显得力不从心了:

image-20220612100905475

由于哈希表不能发挥作用,所以最终还是沦为顺序查找——索引并没有起到作用。

综上:直接给出一个值进行查找,使用哈希表是很好的;但是若查询是基于一个范围的,那么我们就需要寻找其他方法了。

 

排序二叉树

排序二叉树的原理

排序二叉树虽然名字中是排序,但它的主要用途却是查找,因此又称为二叉查找树。它可以看成线性表中链表的变形,而在它上面的查找也可以看成二分查找的特殊化。

image-20220611214742539

图3 排序二叉树

排序二叉树的定义是递归的:

二叉排序树(Binary Sort Tree)又称二叉查找树,它是一种特殊的二叉树,它或为空树,或具有以下性质的二叉树:

  1. 它的右子树非空,则右子树上所有节点的值都大于根节点的值。
  2. 它的左子树非空,则左子树上所有节点的值都小于根节点的值。
  3. 左右子树各是一颗二叉排序树。

我们当前指向的结点可以看成二分查找的中间结点;通过大小判断,我们可以选择走左子树或右子树,这和二分查找每次折半的思想是一致的。可以说,排序二叉树是二分查找算法衍生出的一种数据结构。

而之前分析二分查找的时候留了个疑问:

还有什么数据结构能够高效地进行查找,同时插入和删除也比较方便呢?

排序二叉树的性能分析

我们首先来分析排序二叉树的插入。由于每次插入的结点都是叶子结点,所以都要移动到二叉树的底部,对应的时间复杂度就是排序二叉树的高度,数量级为O(logn)

同时它上面的查找和二分查找相似,时间复杂度为O(logn)。可见它已经基本解决我们之前的问题了。但是,排序二叉树本身还存在这样的问题:

由于插入数据的大小和顺序是不确定的,所以构造出的排序二叉树的结构也是不确定的,它有可能变成一个单链表:

image-20220611220120300

图4 排序二叉树变为单链表

这样就失去了它树形结构的优势了,最终的性能和线性表一样。

所以我们应该如何保持它的树形结构,将二叉树的高度压缩到最小?

 

平衡二叉树

平衡二叉树的原理

平衡二叉树AVL在排序二叉树的基础上增加了下面的限制条件:

左右子树深度差绝对值不能超过 1。

这样AVL的高度就可以压缩到最小,不会出现图4的情况。我们可以将每个结点的平衡系数标记在结点处:

image-20220611233312933

图5 平衡二叉树

平衡二叉树的性能分析

由于平衡二叉树自身的约束条件,每次插入后一般都要进行调整:

image-20220611234048473

图6 左旋调整

image-20220611234114795

图6 右旋调整

由于需要进行左旋、右旋等调整,最终平衡二叉树插入的时间复杂度介于(O(log2N),O(n))之间。同时由于平衡二叉树的高度压缩到最小,所以查询的效率是比较稳定的。

因为数据库中读写操作比例大概为10:1,平衡二叉树牺牲了部分插入的时间换取了查找操作的稳定性能,不失为数据库索引的一种比较具有优势的数据结构。

现在我们离结果已经很近了。我们接下来看看数据库中实际使用的B树和B+树。

 

B 树与B+树

B树与B+树是数据库索引实际使用的数据结构,不同的数据库管理系统和数据库引擎要么使用B树,要么使用B+树。研究这两种树的结构,对我们进一步理解数据库的存储系统具有很大的帮助。

B 树

B树的结构

B树又被称为多路平衡查找树,B是Balance的意思。它也是一种平衡的树,但是和二叉树不同,它是多叉的。从二叉树的"瘦高"结构变为了多叉树的"矮胖"结构。

image-20220612000001397

图7 多路平衡查找树

它的特点如下:

  1. 根结点至少有两个子结点;
  2. 每个中间节点都包含 k-1 个元素和k个子结点,其中 m/2 <= k <= m;
  3. 每一个叶子结点都包含 k-1 个元素,其中 m/2 <= k <= m;
  4. 所有的叶子结点都位于同一层;
  5. 非叶子结点的key都是[key,data]二元组,其中key表示作为索引的键,data为键值所在行的数据;同一结点的key从小到大排列。

B树的查找性能分析

image-20220612000517010

图8 B树查找例子

加入我们要从这样一棵树中查找15,经过的步骤如下:

  1. 因为15小于17,走左边。
  2. 因为15大于12,走右边。
  3. 在磁盘块7里面就找到了15。

它的查找性能也是O(logn)的数量级,只是底数一般都大于2,查找性能比AVL更高。

采用B树的原因

实际的数据库采用B树,而没有采用平衡二叉树,有以下原因:

  1. B树的查找效率比AVL树更高。
  2. B树的查找减少了与磁盘的IO次数,大大减少了访问磁盘的时间开销。
  3. B树更节约存储空间。

第二个原因比第一个更重要。因为数据库的数据是存储在磁盘中的,每次查找时都要从磁盘中读取数据。由于从机械硬盘中读取数据需要 10ms 左右的寻址时间,交互次数越多,消耗的时间就越多。最终寻址的时间可能会占到查找时间的大部分。所以需要从减少磁盘访问次数下手。

第三个原因是由DBMS的存储结构导致的。因为数据库操作磁盘的大小以页为单位,一页的大小为16K,所以树的每个结点大小至少为16K。但是,一个索引存储的仅仅是 键值+数据+引用,远远达不到16K,所以使用二叉树结构会造成空间的大量浪费。而多叉树一个结点存储了多个索引的信息,空间利用率高。

 

B+树

B+树是B树针对数据库特点的进一步优化。因为数据库更多地使用到范围查询,而B树要按大小顺序访问元素的话就必须要进行中序遍历,或者先访问到第一个元素,然后从它开始进行中序回溯,显然这是比较麻烦的。

B+树使用双向指针将元素串接起来,要访问某个范围的元素,只需顺着指针访问即可:

image-20220612002539407

图7 B+树

它的特点如下:

  1. B+Tree中的非叶子结点不存储数据,只存储键值;
  2. 所有键值都会出现在叶子结点上,且key存储的键值对应data数据的物理地址;
  3. B+Tree搜索到键值不会直接返回,会到最后一层的叶子节点;
  4. B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数 据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

此外,由于每次查找必须访问到叶子结点,而所有叶子结点都在同一高度上,所以它的查找性能是很稳定的,不会因为数据出现的位置而浮动。

相比于B树,B+树还有一个优势就是非叶子结点全部存储键和指针,而不存储数据。所以一个结点的索引数可以进一步增加,树的高度可以进一步减小,从而进一步减少磁盘IO。

一般来说,B+树2~3层就能存储千万级别的数据了。

 

结语

这篇文章,我们从最基本的二叉查找开始研究,再分析索引查找存在的不足;然后从排序二叉树分析到平衡二叉树,最后研究了数据库中实际采用的B树和B+树,分析了数据库使用这两种数据结构的原因,并对二者进行了对比。可以感受到,数据库也是在不断发展的,而它的发展,离不开数据结构与算法的支撑。数据结构与算法在计算机科学类与至关重要。

 

参考文献

[1] 百度百科编者.数据库索引.百度百科,2020(2020-11-24) [2021-01-09]. https://baike.baidu.com/item/数据库索引/8751686 [2] 算法导论.Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein 著 [3] 算法(第四版).Robert Sedgewick,Kevin Wayne 著.谢路云 译 [4] MySQL探秘(三) MySQL索引原理.Prince Li 著.https://princeli.com/mysql探秘三mysql索引原理/ [5] 为什么 B+ 树比 B 树更适合应用于数据库索引?.力扣专栏作者 著.https://leetcode.cn/circle/discuss/F7bKlM/ [6] 为什么 MySQL 使用 B+ 树.面向信仰编程.https://draveness.me/whys-the-design-mysql-b-plus-tree/ [7] 数据库中的机器学习:哈希表、B 树与学习索引.YEY Blog.https://yey.world/2020/08/21/LearnedIndex-02/