首页 新闻资讯 地被苗圃
数据库索引技术之B树索引
发布日期:2022-08-07 06:20    点击次数:164

本文转载自微信公众号「小菜学编程」,作者fasionchan 。转载本文请联系小菜学编程公众号。

前面我们介绍了 哈希索引 和 LSM树索引 ,它们都基于日志结构式的数据文件。虽然工程界对这种索引的认可度正与日俱增,但还远不是最受欢迎的索引技术。

那么,目前应用最广的索引技术又是什么呢?

您可能早就有所耳闻——这就是本文要探讨的 B树( b-tree )索引。B树可以说是数据库索引技术中的武林盟主,能够几十年长盛不衰,必定有它自己的独门秘诀。

索引结构

跟我们在 LSM树 一节中提到的 SSTable 一样,B树也是将数据组织成有序形式,因此支持范围查询。尽管如此,它们的底层结构却完全不同,B树有自己独特的设计哲学。

日志结构式索引将数据分成大小可调节的分段,通常是几兆或更大,然后再顺序写入磁盘。而B树则是以 块( block )为单位来组织数据,块大小是固定的,通常是 4KB ,也可以更大。这种设计更贴近磁盘的硬件结构,因为磁盘也是以块为单位来读写数据的。

出于性能方面考虑,计算机通常以一定字节数(如 4KB )为单位来存取数据。在不同的场景有不同的叫法:磁盘数据一般称为 块 ( block ),内存数据一般称为 页( page )。这两种场景数据库均有涉及,因而术语可以混用。

磁盘中的每个数据块都有一个唯一的地址,因此数据块间可以互相引用,有点像内存中的指针。因此,我们可以用这种方式,将数据块组织成一棵树——B树( b-tree )。

如上图,为简化讨论,我们假设数据库记录只有两个字段:一个是索引键,类型为整数;另一个是值。数据按索引键排序,依次保存在一个数据块中,如蓝色数据块所示。

紫色部分数据块为索引,它将索引键的范围划分为多个区间;每个区间保存着另一个数据块的地址( ref ),表示该范围内的数据,可以通过 ref 指向的数据块找到。上图中红色的 ref 表示, 之间的数据,可以通过其左下方的另一个索引数据块找到。

如果子范围内的数据记录还很多,单个数据块容纳不下,ref 便指向另一个索引块,进一步将数据范围分小;如果子范围内的数据记录不多,一个数据块就能装下,ref 便直接指向数据。

这样一来,ref 就将数据块组织成一棵多叉树,数据块主要分为两种:

一种用于保存数据记录,如上图蓝色部分,位于树的 叶子节点 ,简称 数据块 ; 一种用于保存索引,如上图紫色部分, 拖车视频位于树的的 内部节点,简称 索引块 ;

从树的根节点索引块出发,根据数据键所在范围的 ref 逐层往下找,即可定位到数据记录。举个例子,当查询键为 400 的记录时,搜索路径如绿色箭头线所示:

从根索引块出发,400 落在区间 [343, 470) ,根据该区间 ref 找到下一级;

来到下一个索引块,400 落在区间 [384, 412) ,根据该区间 ref 找到下一级;

最终来到蓝色的数据块,待查找的数据记录就在里面;

范围查询

为了支持范围查询,数据库将数据记录排过序后才保存到数据块,相邻数据块间则通过双向链表指针连接在一起。

这样一来,数据库只要先定位边界元素,然后以此为起点遍历数据即可:

如果查询条件为小于,则从后往前遍历数据;

如果查询条件为大于,则从前往后遍历数据;

如上图,以查询大于等于 400 且小于 420 的数据为例:

数据库定位到键值为 400 的数据记录,如红框所示;

数据库检查本数据块内 400 以后的记录,满足小于 420 则取出;

数据库根据链表指针找到下一个数据块,继续检查里面的数据记录,满足小于 420 则取出;

数据库重复步骤 3 ,逐个往后遍历数据块,直到有数据记录大于等于 420 ;

分支因子

我们注意到,B树是一种多叉树。那么,为什么不能用最简单的二叉树呢?

实际上,每个树节点最多可以有多少个分叉,是树的一个非常重要的特性—— 分支因子( branching factor )。我们知道,在数据记录数一定的前提下,树的分支因子越大,高度越低。

我们使用排序树来查找数据时,从根节点开始不断搜索,最终来到叶子节点。换句话讲,我们需要检查的节点数,其实就是树的高度。

而数据库数据需要持久化并保存在磁盘里面,那磁盘有什么特点呢?

磁盘 IO 比较慢,非顺序的磁盘 IO 更是如此; 磁盘 IO 以 块( block )为数据单位,单次 IO 总是读写整个块;

在排序树中搜索数据,显然是离散读,而不是顺序读。因为我们无法保证 ref 指向的数据块就在当前块后面,磁盘通常只能重新 寻道( seek )后才能读取数据。由于磁盘寻道很慢很慢,IO 次数必须尽量减少,因此树的高度应该尽量压低。

另一方面,磁盘以块为单位读写数据,一个块可以保存很多分支信息。如果一个块只保存两个分支,那就浪费了。因为就算只保存两个分支,读的时候还是必须整块读,开销是一样的。因此,不如尽量提高分支数,这样还能减低树的高度,进而减少 IO 次数。

通常 4KB 大的数据块可以保存多达 500 个分支,如果树的高度为 3 ,可以支撑多达 个数据,超过一亿。有意思的是数据库根索引块通常缓存在内存中,这样只需 2 次 IO 操作即可从超过 1 亿数据中找到想要的那个。

综上所述,B树几乎就是为磁盘量身定制的数据结构,它充分地利用了磁盘的特点:

磁盘以块为单位读写数据,B树就以块为节点,组织成多叉树;

磁盘 IO 很慢,B树就通过提高分支因子,降低树的高度,减少 IO 次数;

写操作

数据库写操作分为两种,一种是 更新( update ),一种是 插入( insert )。

如果要更新数据库中的已有记录,先搜索B树找到包含该记录的数据块(叶子节点)。然后修改数据块的记录值,再将个数据块写回磁盘。由于数据块只是内容改变了,位置不变,因此B树中任何对该数据块的引用仍然有效。

如果要插入一条新记录,同样先搜索B树,找到数据范围包含新记录的数据块(叶子节点)。如果数据块还有足够空间,就将新记录添加进入并保存到磁盘即可。如果数据块空闲空间不足,则需要将其分裂为两个:

如上图,以插入 399 为例:由于目标数据块已经存满,需要将其分裂为两个。分裂后的数据块都只有一半数据,新记录保存在其中的一个。

如果新记录的键相对较小,则保存在左边的数据块;否则就保存在右边的数据块。399 跟该范围的其他数据相比较小,因此保存在左边数据块。

由于数据块发生了分裂,因此它们的父节点需要更新,以便记录最新的数据范围和分支信息。

B树算法可以保证树的 平衡( balanced ):一棵包含 个键的B树,高度不超过 ,否则树的性能会大打折扣。通常一棵 3 层或 4 层深的B树即可容纳数据库所有数据,因此查询时无须遍历太多数据块,性能相对较好。

至此,三种主流的数据库索引技术已经全部介绍完毕。除了本节介绍的B树索引,其他两种分别是:

 

哈希索引 LSM树索引

 



Powered by 北京地球天使环保科技有限公司 @2013-2022 RSS地图 HTML地图