手写一个简单的Database7

Part 7 B-Tree简介

B-tree是SQLite用来表示表和索引的数据结构，所以B-tree是非常中心的想法。这个主题主要是介绍B-tree数据结构，所以不会有任何的代码。

成都创新互联专注于企业营销型网站建设、网站重做改版、冠县网站定制设计、自适应品牌网站建设、H5场景定制、商城网站制作、集团公司官网建设、外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为冠县等各大城市提供网站开发制作服务。

为什么说对于数据库来说，树是非常好的数据结构呢？

• 查找特定的value很快（对数时间花销，loga N）
• 插入一行或者对查询到的数据删除很快（再平衡使用常量时间）
• 遍历一个范围内的value很快（不像hash map）
• B-tree不同于二叉树（“B”可能代表发明人的名字，但也可以代表“Balanced”）。这里是一个B-tree例子：

B-Tree 例子(https://en.wikipedia.org/wiki/File:B-tree.svg)

不像二叉树每个节点只能有两个子节点，B-tree的每个节点可以有两个以上的子节点。每个节点最多可以有 m 个子节点，其中 m 叫做树的“order”（或者叫“阶”）。为了保持树的尽量平衡，我们还要求节点必须至少有 m / 2 个子节点（四舍五入）。

但还有一些例外：

• 叶子节点没有子节点
• 根节点的子节点数可以少于m，但至少要有两个
• 如果根节点也是叶子节点（树只有一个节点），那它有0个子节点

上面的描述的是一个B-tree，SQLite用它来存储索引。为了存储表数据，SQLites使用一种B-tree的变体，称为B+tree。

在我们开始实现索引之前，我将只讨论B+tree，但这里将其称为 B-tree 或者 btree。

有子节点（children）的节点被称为“内部”节点（internal node），内部节点和叶子节点在结构上不同：

这里通过一个例子来看一下，当插入一个元素时，B-tree是怎样发生结构变化的。为了让事情看起来更容易理解，这棵B-tree的阶（order）设置为3(m=3)，也就是说：

• 每个内部节点最多有三个子节点(m)
• 每个内部节点最多有两个key
• 每个内部节点至少两个子节点（m-1）
• 每个内部节点至少一个key

一棵空树只有一个节点：根节点。根节点最开始也作为叶子节点，有0个键值对（key/value）：

空的btree

如果我们插入两个键值对（超过两个键值对，节点需要分裂，参考上面规则），他们会按顺序排序存放在叶子节点中。

一个节点的btree

我们假设了节点的容量是两个键值对儿。当我们插入另外一个的时候，就不得不分裂叶子节点了，分裂后的两个节点每个存放之前一半的键值对。分裂后的两个节点都变成了内部节点，同时也变成了一个新的节点的子节点，这个新的节点变成了根节点。

两层的btree

图中的内部节点（也是根节点）有一个key和两个指针指向子节点（就是那两条线）。如果我们想查找一个key，key小于或等于5，我们查看左子树。如果查找的key大于5，就查看右子树。现在，准备插入一个新的key "2"。首先，我们查找它将位于哪个叶节点（如果它在树中存在的话），这样就到达了左侧叶子节点。这个节点是满的，所以把这个叶子节点进行分裂（split），并在父节点创建新的条目。

四节点的btree

现在继续增加key，18 和 21 。现在又到了不得不分裂的情况，但是在父节点中已经没有空间来增加新的键值对儿了。

内部节点没有空间

解决方法就是分裂根节点为两个内部节点，然后创建一个新的根节点作为两个内部节点的父节点。

三层的btree

树只是在我们分裂根节点的时候才会增加深度。每个叶子节点都有相同的深度和接近相同的数量的键值对儿，所以树能够保持平衡和快速的进行查找。

我暂时先不讨论从树中删除键的操作，推迟到实现插入操作以后。

当我们实现这个数据结构时，每个节点都对应一个page。根节点将在page0中存在。节点中的子节点指针将简单的使用包含子节点的page number。

网页题目：手写一个简单的Database7
当前地址：http://www.mswzjz.cn/qtweb/news37/487537.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能