B/B+ 树及数据库索引应用

B-树

定义:B-树是一类树,包括 B-树、B+树、B* 树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是 B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

为什么会出现 B-树这类数据结构?
  传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。
  原因是当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50ns,而磁盘在 10ms 左右,相差了近 5 个数量级。这说明程序大部分时间会阻塞在磁盘 IO 上。
  那么我们如何提高程序性能?减少磁盘 IO 次数。像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
  平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log2n,这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

从“迎合”磁盘的角度来看看 B-树的设计
  索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。
  那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4k,8k或 16k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

上图是一棵简化的 B-树,多叉的好处非常明显,有效的降低了 B-树的高度,为底数很大的 logn。一般一棵 B-树的高度在 3 层左右。
B-树的每个节点是 n 个有序的序列(a1, a2, a3, … , an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1 < X2 < a2 < … < an < Xn+1)。

一个 m 阶的 B-树满足以下条件

  1. 有 k 棵子树的分支结点存在 k-1 个关键码,关键码按照递增次序进行排列;
  2. 根结点至少拥有两颗子树(存在子树的情况下),至多拥有 m 棵子树;
  3. 除了根结点以外,每个结点至多拥有 m 棵子树,其余每个分支结点至少拥有 m/2 棵子树(即关键字数量 n 需要满足 ⌈m/2⌉-1 ≤ n ≤ m-1);
  4. 所有的叶结点都在同一层;

B-树的查找
我们来看看 B-树的查找,假设每个节点有 n 个 关键字,被分割为 n+1 个区间,注意,每个 关键字紧跟着 data 域,这说明 B-树的关键字和 data 是聚合在一起的。一般而言,根节点在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索关键字为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断关键字 25 小于关键字 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该关键字为止。

一个酷炫的网页,可以自己插入删除节点,观察 B-树的变化情况:
https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-树的插入规则
新结点一般插入在最底层,通过搜索找到对应的结点进行插入,根据即将插入的结点的关键字数量又分为下面几种情况:

  • 如果该结点的关键字个数没有到达 m-1 个,那么直接插入即可;
  • 如果该结点的关键字个数已到达了 m-1 个,无法满足 B-树的性质,需要将其进行分裂。分裂的规则是该结点分成两半,将中间的关键字提升到父亲结点中,这又可能导致父节点的分裂,那就继续向上回溯(甚至是要对根结点进行分裂,那么整棵树都加了一层)。

过程如下:

B-树的删除规则
先通过搜索找到相应的值,存在则进行删除:

  • 如果该结点拥有关键字数量仍然大于或等于 ⌈m/2⌉-1,则不做任何处理;
  • 如果该结点在删除关键字以后,关键字数量小于 ⌈m/2⌉-1,则需要向兄弟结点借关键字,这又分为兄弟结点的关键字数量是否足够的情况:
    • 如果兄弟结点借出一个关键字仍满足 B-树性质,则将该节点与兄弟节点之间夹的父亲结点关键字下移,兄弟结点的关键字上移;
    • 如果兄弟结点的关键字在借出以后无法满足情况,那么我们可以将该结点合并到兄弟结点中,合并之后的子结点数量少了一个,则需要将父亲结点的关键字下放,如果父亲结点不满足性质,继续向上回溯;

过程如下:

B+树

B+树是 B-树的变种,它与 B-树的不同之处在于:

  1. 在 B+树中,关键字的副本存储在内部节点,真正的关键字和 data 存储在叶子节点上(所有的 data 都在最后一层)。
  2. n 个关键字的节点指针域为 n 而不是 n+1。

每个节点关键字的数量范围依然是 ⌈m/2⌉-1 ~ m-1,顺序递增。

因为内节点并不存储 data,所以一般 B+树的叶节点和内节点大小不同。为了增加区间访问性,一般会对 B+树做一些优化。如下图带顺序访问的 B+树:

B+树的插入删除类似于 B-树。

B-树和 B+树的区别

1、B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 logn。而 B-树查询时间复杂度不固定,与关键字在树中的位置有关,最好为 O(1)

如下所示 B-树/B+树查询关键字为 50 的 data。

B-树

关键字为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。


B+树

由于 B+树所有的 data 域都在根节点,所以查询关键字为 50 的节点必须从根节点索引到叶节点,时间复杂度固定为 O(logn)。


2、B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而 B-树每个节点关键字和 data 在一起,则无法区间查找

根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

B+树可以很好的利用局部性原理,若我们访问节点关键字为 50,则关键字为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数
当然 B+树也能够很好的完成范围查询。比如查询关键字在 50~70 之间的节点。


3、B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确。
由于 B-树节点内部每个关键字都带着 data 域,而 B+树节点只存储 key 的副本,真实的关键字和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,这就意味着B+树单次磁盘 IO 的信息量大于 B-树,从这点来看 B+树相对 B-树磁盘 IO 次数少。

为什么 MongoDB 索引选择 B-树,而 Mysql(InnoDB 引擎)索引选择 B+树

MongoDB 是文档型的数据库,是一种 NoSQL,一般使用 XML 或 Json 格式来保存数据,归属于聚合型数据库。被设计用在数据模型简单,性能要求高的场合。MongoDB 是聚合型数据库(通常就是键值对),而 B-树恰好关键字和 data 域聚合在一起。
Mysql 是一种关系型数据库,区间访问是常见的一种情况,而 B-树并不支持区间访问,B+树由于数据全部存储在叶子节点,并且通过指针串在一起,这样就很容易的进行区间遍历甚至全部遍历,且每个节点能索引的范围更大更精确。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,784评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,745评论 2 378
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,702评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,229评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,245评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,376评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,798评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,471评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,655评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,485评论 2 318
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,535评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,235评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,793评论 3 304
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,863评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,096评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,654评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,233评论 2 341

推荐阅读更多精彩内容

  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,140评论 0 25
  • B树 1.前言: 动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balan...
    铁甲依然在_978f阅读 1,443评论 0 4
  • 原文链接 B树 1.前言: 动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(...
    非典型程序员阅读 1,139评论 0 3
  • 2017年5月11日 晴 忆起儿时的艰苦,咱家属于超生游击队,理所当然的就成为了全村最穷的贫困户,妈妈从小只...
    东尼日记阅读 169评论 0 0
  • 1 说起写文章,已经很久没有写了,碎片化时间太多,写不出来,还记得15年的时候坚持过一段时间,还是放弃了,多了真的...
    俊阳中医康复阅读 272评论 0 0