B-树和B+树

参考链接:
MySQL索引背后的数据结构及算法原理
B树、B-树、B+树、B*树

1.B-Tree

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

  • d为大于1的一个正整数,称为B-Tree的度。
  • h为一个正整数,称为B-Tree的高度。
  • 每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。
  • 子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。
  • 所有叶节点具有相同的深度,等于树高h。
  • key和指针互相间隔,节点两端是指针。
  • 一个节点中的key从左到右递增排列。
  • 如果某个指针在节点node的左右相邻key分别是key1和key2且不为null,则其指向的节点的所有key小于key2且大于key1.
    下图是一个B-Tree:
Paste_Image.png

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。

另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法。

2.B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。
与B-Tree相比,B+Tree有以下不同点:

  • 每个节点的指针上限为2d而不是2d+1。
  • 内节点不存储data,只存储key;叶子节点不存储指针。
  • 非叶子结点的子树指针与关键字个数相同;
  • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-Tree是开区间
  • 为所有叶子结点增加一个链指针;

下面是一个简单的B+Tree示意。

Paste_Image.png

一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关。
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图中如果要查询key为从20到33的所有数据记录,当找到20后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,290评论 0 25
  • 用途:Mysql数据库里面的索引主要基于Hash和B+树。 B-树 (读作B shu,中间不是减号)一句话总结:就...
    徐超Change阅读 1,552评论 1 4
  • 原文链接:MySQL索引背后的数据结构及算法原理 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题...
    加油小杜阅读 882评论 0 8
  • 在学习数据结构的时候,往往学习的思路是直奔主题,学习各种大神们设计出来的结构精妙的数据结构。但是,这样的学习方式使...
    littlelory阅读 3,159评论 6 12
  • 你在哪里,你在哪里,你在哪里 穿过时空的隧道 我声声呼唤 你踏上了漫漫征程 走出远古 绕过雪山 越过冰川 穿过荒蛮...
    艾洛莉娅瑞雪儿阅读 215评论 0 0