B树、B+树、B*树

说起数据库,避免不了的要讲索引。要真正理解索引,首先就得清楚B+树的结构等

B树

B树即B-树,而不是两种树。

概念:一棵m阶B树是一棵平衡的m路搜索树。
特点:

  • m即所有节点中孩子节点个数的最大值
  • 每个非根节点所包含的关键字个数j满足:ceil(m/2) - 1 <= j <= m - 1(ceil为向上取整,即大于该数的最小整数)
  • 节点的子节点数会比关键字个数加1
  • 根据以上两条可以得出,每个节点最多有m个分支,非根非叶节点至少有ceil(m/2)个分支

B树的查找

B树的查找还是很简单的,不再赘述。

其最低搜索性能:

B树的插入

例:用1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15构建5阶B树

因为构建5阶的B树,所以每个节点的关键字个数范围为[2,4]

插入11时,该节点的关键字个数超出范围,进行分裂

之后直接插入4,8,13

当插入10时,节点关键字个数再次超出范围

将子节点分裂

直接插入5,17,9,16,插入20

关键字个数超出范围,进行分裂

继续插入3

关键字个数超出范围,进行分裂

继续插入15

关键个数超出范围,进行分裂

这时候根节点关键字个数也超出范围,继续分裂

B树的删除

对于B-树关键字的删除,需要找到待删除的关键字,在结点中删除关键字的过程也有可能破坏B-树的特性,如旧关键字的删除可能使得结点中关键字的个数少于规定个数,这是可能需要向其兄弟结点借关键字或者和其孩子结点进行关键字的交换,也可能需要进行结点的合并,其中,和当前结点的孩子进行关键字交换的操作可以保证删除操作总是发生在终端结点上。

从上面已经构建好的B树中依次删除8,16,15,4

删除8:关键字8在叶子节点上,并且删除后其所在结点中关键字的个数不会少于2,因此可以直接删除。


删除16:关键字16不在终端结点上,但是可以用17来覆盖16,然后将原来的17删除掉


删除15:15虽然也在终端结点上,但是不能直接删除,因为删除后当前结点中关键字的个数小于2。这时需要向其兄弟结点借关键字,显然应该向其右兄弟来借关键字,因为左兄弟的关键字个数已经是下限2.借关键字不能直接将18移到15所在的结点上,因为这样会使得15所在的结点上出现比17大的关键字,所以正确的借法应该是先用17覆盖15,在用18覆盖原来的17,最后删除原来的18


删除4:4在叶子节点上,但是此时4所在的节点的关键字个数已经到下限,需要借关键字,不过可以看到其左右兄弟节点已经没有多余的关键字可借。所以就需要进行关键字的合并。可以先将关键字4删除,然后将关键字5、6、7、9进行合并作为一个节点链接在关键字3右边的指针上,也可以将关键字1、2、3、5合并作为一个节点链接在关键字6左边的指针上

显然上述两种情况下都不满足B-树的规定,即出现了非根的双分支节点,需要继续进行合并

B+树

一棵m阶B+树是一棵平衡的m路搜索树

  • 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
  • ceil(m/2) <= j <= m
  • 所有的叶子节点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接(叶子节点之间增加了横向的指针)。
  • 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。【在这一点上有一些不同的说法,其中一种说法为,非叶子结点的子树指针与关键字个数相同,非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)】

按不同的说法,以上两种形式的B+树应该都对

B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

B+树的查询

B+树的好处就体现在查询性能上:

  • 在单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。比如拿上面的B+树来进行查询:

现在要查找3:
第一次磁盘IO:

第二次磁盘IO:

第三次磁盘IO:

看到这里,可能会觉得查询流程和B-树差不多呀。
不,有两点不同。首先,B+树的中间节点没有数据,只存储索引,所以同样大小的磁盘页可以容纳更大的节点元素。这就意味着,数据量相同的情况下,B+树比B-树更加“矮胖”,因此查询时IO次数也更少。
其次,B+树的查询必须最终查询到叶子节点,而B-树只要找到匹配元素即可,无论匹配元素在叶子节点还是在中间节点。因此,B-树的查找性能并不稳定(最好的情况只查找根节点,最坏的情况查找到叶子节点)。而B+树的每一次查找都是稳定的。

B+树查询的优势更多的体现在范围查询上。比如现在要查询3-11的元素。
B-树的查找过程:
自顶向下查找到范围的下限3:

中序遍历到元素6:

中序遍历到元素8:

中序遍历到元素9:

中序遍历到11,遍历结束:

B-树的范围查询是不是很繁琐呢?
再来看看B+树的范围查询。
自顶向下查找到范围的下限3:

通过链表指针,遍历到元素6,8:

通过链表指针,遍历到元素9,11,遍历结束:


总结一下B+树的特征和优势

B+树的特征:
1、有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有元素都保存在叶子节点。
2、所有的叶子节点中保存了全部元素的信息,及指向含这些元素记录的指针,且叶子节点本身依关键字的大小自小而大顺序链接。
3、所有的中间节点元素都同时存在于子节点,在子节点元素节点中是最大(或最小)元素。

B+树的优势:
1、单一节点存储更多的元素,使得查询的IO次数更少。
在数据库检索来说,对于磁盘IO扫描时最消耗时间的,因为磁盘扫描涉及很多物理特性,这些是相当消耗时间的。所以B+树设计的初衷就是最大限度的减少对于磁盘的扫描次数。如果一个表或索引没有使用B+树(对于没有聚集索引的表是用堆heap存储),那么查找一个数据,需要在整个表包含的数据库页中全盘扫描。这无疑会大大加重IO负担,而使用B+树进行存储,则仅仅需要将B+树的根节点存入内存中,经过几次查找后就可以找到存放需要数据的被叶子结点包含的页,进而避免了全盘扫描从而提高了性能。
2、所有查询都要查询到叶子节点,查询性能更稳定。
3、所有叶子节点形成有序链表,便于范围查询。

B+树的插入

1)若为空树,创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。
2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入记录。插入后,若当前结点key的个数小于等于m-1,则插入结束。否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2+1个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第3步。
3)针对索引类型结点:若当前结点key的个数小于等于m-1,则插入结束。否则,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第3步。

往下图的3阶B+树中插入9

首先查找9应插入的叶节点,插入发现没有破坏B+树的性质,插入完毕。


往下图的3阶B+树中插入20

首先查找20应插入的叶节点,插入:

发现第二个叶子节点已经破坏了B+树的性质,则分解成[20,21],[37,44]两个,并把21往父节点移。

发现父节点也破坏了B+树的性质,则把父节点再分解成[15,21],[44,59],并把21往父节点移。


往下图的3阶B+树插入100

首先查找100应插入的节点,插入

修改其所有父节点的的键值为100(只有插入比当前树的最大数大的数时要做此步骤)

拆分节点

B+树的删除

删除下图3阶B+树的关键字91

首先找到91所在的节点,删除,没有破坏B+树的性质,完毕


删除下图3阶B+树的关键字97

首先找到97所在的叶子节点,删除,然后修改该节点的所有父节点的关键字为91(只有删除树中最大的关键字需要做此步骤)


删除下图3阶B+树的关键字51

首先找到51所在的叶子节点,删除

破坏了B+树的性质,向该节点的兄弟节点(左节点或右节点)借节点44,并修改相应键值。


删除下图3阶B+树的关键字59

首先找到59所在的叶子节点

破坏B+树的性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树的性质),合并第二、第三叶节点,并调整键值


删除下图3阶B+树的关键字63

首先找到63所在的叶节点,删除

合并第四、第五节点并调整键值

第二层的第二个节点不满足B+树的性质,从第二层的第一个节点借59并调整键值

B*树

B*树是B+树的变体,在B+树的非根非叶子节点中再增加指向兄弟节点的指针。B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

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

推荐阅读更多精彩内容

  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,202评论 0 25
  • B-树,就是B树,B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一...
    xx1994阅读 23,689评论 1 17
  • B树 1.前言: 动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balan...
    铁甲依然在_978f阅读 1,446评论 0 4
  • 在CSS2.1里,background属性的简写方式包含五种属性值,从CSS3开始,又增加了3个新的属性值,加起来...
    水玲珑_44a9阅读 11,467评论 0 2
  • 合法行政,合理行政,诚实守信原则,程序正当选择,高效便民原则,权责正当原则
    010ed0d5a362阅读 325评论 0 0