- 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社区助手微信好友，发送验证信息加群。