关系数据库是如何工作的(2)

数组,树和哈希表

现在我们已经明白了时间复杂度和排序的思想,接下来我要告诉你三个数据结构。这些数据结构都很重要,因为它们是现代数据库的骨架。我也会引入数据库索引这一概念。

数组

二维数组是最简单的数据结构。表格可以被当成是一个数组。例如:

 

数组

这个二维数组就是带有行和列的表格:

  • 每一行表示一个对象
  • 每一列描述对象的特征
  • 每一列存储一种特定的数据类型(整型,字符串,日期等)

虽然这种数据结构非常适合与保存和数据可视化,但是当你需要查找一个特定值时,这种结构就玩不转了。

例如,如果你想找到所有在英国工作的人,你需要遍历每一行,去看看这一行是不是属于英国。这需要消耗 N 个操作(N 是行数),这看起来还不算很坏,但是有更快的吗?这就是引入树的目的。

注意,大多数现代数据库提供了改进数组,用于有效存储表,例如堆组织表(heap-organized tables)和索引组织表(index-organized tables)。但是,这些并不能改变快速检索符合特定条件的列组的问题。

树和数据库索引

二叉搜索树是带有特殊属性的二叉树,其每个节点的键必须满足:

  • 大于所有左侧子树的键
  • 小于所有右侧子树的键

下面我们来看看这是什么意思。

思想

BST

 

这棵树有 N=15 个元素。假如说我要查找 208:

  • 我从根节点开始找起,根节点的键是 136。由于 136<208,那么,我需要查找节点 136 的右侧子树
  • 398>208,那么,我需要查找节点 398 的左侧子树
  • 250>208,那么,我需要查找节点 250 的左侧子树
  • 200<208,那么,我需要查找节点 200 的右侧子树。但是 200 没有右侧子树,因此,该值不存在(因为如果它存在,它应该在 200 的右侧子树)

现在,我要找 40:

  • 我从根节点开始找起,根节点的键是 136。由于 136>40,那么,我需要查找节点 136 的左侧子树
  • 80>40,那么,我需要查找节点 80 的左侧子树
  • 40= 40,节点存在。我取出该节点中保存的行号(这一属性没有在上图展示出来),找到了给定行号的表
  • 知道了行号,也就知道了数据在表中的确切位置,因此我就能直接取出。

最后,这两个检索都只耗费了树的层数那么多的操作。如果你认真阅读了合并排序的部分,你应该发现这棵树其实是有 log(N) 层。所以,检索消耗是 log(N),还不错!

回到问题

这些解释都有点抽象,让我们回到我们的问题。忘记前面愚蠢的整数吧,我们想想前面的表格中那些代表某人所在国家的字符串。加入你有一棵包含了表格中“国家”一列的树:

  • 假设你想知道谁在英国工作
  • 查找树,获得表示英国的节点
  • 在那些“英国节点”中,你可以找到这些在英国工作的人所在行的位置

这个检索只会消耗 log(N) 个操作,而直接使用数组则需要 N 个操作。这个你想象中的东西就是数据库索引(database index)。

你可以为列的任意组合构造树索引(字符串、整型、2 个字符串、一个整型和一个字符串、日期等等),只要你能够有一个可以比较键值(也就是这些列的组合)的函数。该函数可以用来计算这些键值的顺序(数据库中的基本类型就是这种情况)。

B+ 树索引

虽然二叉搜索树适合于查找特定值,但是当你需要获取两个值之间的多个元素时,会有一个很大的问题。因为你必须检查树中的所有节点,看它是不是落在两个值之间(例如,使用树的中序遍历),二叉搜索树的消耗会达到 O(N)。更要命的是,由于你必须读取整棵树,因此这一操作不是磁盘 I/O 友好的。我们需要找到一个执行范围查询的有效方法。为解决这一问题,现代数据库使用了一种改进了的二叉搜索树,被称为 B+ 树。在 B+ 树中:

  • 只有最低的节点(叶子节点)保存信息(相关表中的行的位置)
  • 其它节点仅仅用来在检索中路由到正确的节点。

数据库索引

正如上图所示,B+ 树的节点更多(比二叉搜索树多出一倍)。事实上,你有一些额外的节点,这些“决策节点”会帮助你找到正确的节点(也就是保存相关表格行的位置的节点)。然而检索复杂度依然是 O(log(N))(仅仅多了一层)。最大的区别是,最低层节点与它们的后继节点连接起来。

使用 B+ 树,假设你正在查找 40 和 100 之间的值:

  • 你需要像前面的树那样找到 40(如果 40 不存在的话,就选择大于 40 的最小值)
  • 然后通过 40 的后继节点找到 100

假如你找到了 M 个后继节点,而树有 N 个节点。检索特定值就像前面的二叉搜索树一样耗费 log(N);一旦你找到了这个节点,通过它们的后继节点,你会在 M 个操作中找到 M 个后继。该检索仅消耗 M + log(N) 个操作,而前面的二叉搜索树则需要 N 个操作。另外,你不需要一次读取整棵树(只需要 M + log(N) 个节点),这意味着更少的磁盘使用。如果 M 很小(比如 200 行)而 N 很大(1 000 000 行),那就会有很大不同了。

 

但是,还有一些新的问题(又来!)。如果你向数据库新增或删除一行(因此也必须修改关联的 B+ 树索引):

  • 你必须保持 B+ 树中的节点顺序,否则以后就不能在树中查找节点了
  • 你必须尽可能减少 B+ 树的层数,否则时间复杂度就会从 O(log(N)) 变成 O(N)

换句话说,B+ 树必须是自排序的,并且是自平衡的。幸运的是,还真的有智能删除、插入操作。但是这也会导致一个消耗:B+ 树的插入和删除操作都是 O(log(N)) 的。这就是为什么你经常听到这样的话:过多地使用索引不是一个好主意。事实上,由于数据库需要更新表索引,而每一个索引的修改都是 O(log(N)) 的,因此,你正在拖慢原本很快的行插入、更新和删除操作。另外,添加索引意味着会给事务管理器带来更多工作负荷(我们会在文章的最后认识这个管理器)。

更多细节可以阅读百科有关 B+ 树的文章。如果你想要一个数据库中 B+ 树实现的例子,可以阅读 MySQL 的一位核心开发者的这篇文章这篇文章。这两篇文章都关注于 innoDB(MySQL 的引擎之一)的索引处理。

注意:有位读者曾告诉我,考虑到数据库需要进行低层优化,B+ 树必须是完全平衡的。

哈希表

我们最后一个重要的数据结构是哈希表。当你需要快速查找值是,哈希表是非常有帮助的。另外,了解哈希表可以帮助我们理解一个通用的数据库连接操作,被称为哈希连接(hash join)。这种数据结构还被用于存储一些内部信息(比如锁表缓冲池,我们会在后面见到这些概念)。

哈希表是一种使用键快速查找元素的数据结构。构建哈希表需要定义:

  • 元素的
  • 键的哈希函数。键通过哈希函数计算出来的哈希值给出了元素位置(称为)。
  • 用于比较键的函数。一旦找到正确的桶,你需要使用这个比较函数在这个桶中找到你要查找的元素。

 

一个简单的例子

我们看一个可视化的例子:

哈希表

上一篇
下一篇

Comments (3)

  1. hezhongfeng 2016年4月28日
    • 豆子 2016年4月28日
      • hezhongfeng 2016年4月28日

Leave a Reply