共计 2246 个字符，预计需要花费 6 分钟才能阅读完成。
- GreatSQL 社区原创内容未经受权不得随便应用，转载请分割小编并注明起源。
- GreatSQL 是 MySQL 的国产分支版本，应用上与 MySQL 统一。
前文回顾
实现一个简略的 Database1(译文）
实现一个简略的 Database2(译文）
实现一个简略的 Database3(译文）
实现一个简略的 Database4(译文）
实现一个简略的 Database5(译文）
实现一个简略的 Database6(译文）
译注：cstsck 在 github 保护了一个简略的、相似 sqlite 的数据库实现，通过这个简略的我的项目，能够很好的了解数据库是如何运行的。本文是第七篇，次要是对 B -tree 的介绍
Part 7 B-Tree 简介
B-tree 是 SQLite 用来示意表和索引的数据结构，所以 B -tree 是十分核心的想法。这个主题次要是介绍 B -tree 数据结构，所以不会有任何的代码。
为什么说对于数据库来说，树是十分好的数据结构呢？
- 查找特定的 value 很快（对数工夫花销，loga N）
- 插入一行或者对查问到的数据删除很快（再均衡应用常量工夫）
- 遍历一个范畴内的 value 很快（不像 hash map）
B-tree 不同于二叉树（“B”可能代表发明人的名字，但也能够代表“Balanced”）。这里是一个 B -tree 例子：
B-Tree 例子(https://en.wikipedia.org/wiki…)
不像二叉树每个节点只能有两个子节点，B-tree 的每个节点能够有两个以上的子节点。每个节点最多能够有 m 个子节点，其中 m 叫做树的“order”（或者叫“阶”）。为了放弃树的尽量均衡，咱们还要求节点必须至多有 m / 2 个子节点（四舍五入）。
但还有一些例外：
- 叶子节点没有子节点
- 根节点的子节点数能够少于 m，但至多要有两个
- 如果根节点也是叶子节点（树只有一个节点），那它有 0 个子节点
下面的形容的是一个 B -tree，SQLite 用它来存储索引。为了存储表数据，SQLites 应用一种 B -tree 的变体，称为 B +tree。
| B-tree | B+ tree | |
|---|---|---|
| 发音 | “Bee Tree” | “Bee Plus Tree” |
| 用来存储 | 索引 | 表 |
| 外部节点是否存储 key | 是 | 是 |
| 外部节点是否存储 value | 是 | 否 |
| 每个节点的子节点数 | 少 | 多 |
| 外部节点 vs 叶子节点 | 雷同构造 | 不同构造 |
在咱们开始实现索引之前，我将只探讨 B +tree，但这里将其称为 B-tree 或者 btree。
有子节点（children）的节点被称为“外部”节点（internal node），外部节点和叶子节点在结构上不同：
| m 阶 tree | 外部节点 | 叶子节点 |
|---|---|---|
| 存储 | key 和指向子节点的指针 | key 和 value |
| key 的数目 | 最多 m - 1 个 | 越多越好 |
| 指针的数目 | keys + 1 | 无 |
| value 的数目 | 无 | 与 key 的数目雷同 |
| Key 的用处 | 用来路由 | 与 value 成对存储 |
| 存储 value? | 否 | 是 |
这里通过一个例子来看一下，当插入一个元素时，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。
下一次，咱们开始实现 btree。
Enjoy GreatSQL :)
## 对于 GreatSQL
GreatSQL 是由万里数据库保护的 MySQL 分支，专一于晋升 MGR 可靠性及性能，反对 InnoDB 并行查问个性，是实用于金融级利用的 MySQL 分支版本。
相干链接：GreatSQL 社区 Gitee GitHub Bilibili
GreatSQL 社区：
欢送来 GreatSQL 社区发帖发问
https://greatsql.cn/
技术交换群：
微信：扫码增加
GreatSQL 社区助手微信好友，发送验证信息加群。
