Part7B-Tree简介B-tree是SQLite用来表示表和索引的一种数据结构，所以B-tree是一个非常中心的思想。本题主要介绍B-tree数据结构，就不会有代码了。为什么树是数据库非常好的数据结构？查找特定值很快（对数时间成本，logaN）插入一行或删除查询数据很快（重新平衡使用常数时间）遍历一个值范围很快（不像哈希映射）B-tree不像二叉树树（“B”可能代表发明者的名字，但也可以代表“平衡”）。下面是一个B-tree的例子：B-Treeexample(https://en.wikipedia.org/wiki/File:B-tree.svg)不像二叉树，每个节点只能有两个子节点，B-tree每个节点可以有两个以上的子节点。每个节点最多可以有m个子节点，其中m称为树的“顺序”（或“次序”）。为了尽可能保持树的平衡，我们还要求节点必须至少有m/2个孩子（四舍五入）。但也有一些例外：叶节点没有子节点，根节点的子节点个数可以小于m，但如果根节点也是叶节点（树只有一个节点），则至少有两个，则如上所述，它有0个孩子是B树，SQLite使用它来存储索引。为了存储表数据，SQLites使用B树的一种变体，称为B+tree。B-treeB+树读作“BeeTree”和“BeePlusTree”，用于存储索引表。内部节点是否存储密钥？是的？内部节点是否存储值？在我们开始实现索引之前，我只会讨论B+树，但我在这里将它们称为B树或btrees。具有子节点的节点称为“内部节点”。内部节点和叶子节点在结构上是不同的：m阶树内部节点叶子节点存储key和指向子节点的指针以及valuekey的个数最多m-1个，指针key的个数越多越好+1个no的个数value和key的个数不一样key的用途是用来路由和存储value成对存储value的？这里举个例子看看，当插入一个元素时，B-tree的结构是如何变化的。为了便于理解，将这棵B树的阶设置为3（m=3），也就是说：每个内部节点至多有3个子节点（m），每个内部节点至多有两个键每个内部节点至少有两个子节点（m-1）每个内部节点至少有一个键一棵空树只有一个节点：根节点。根节点一开始也作为叶子节点，有0个键值对（key/value）：emptybtree如果我们插入两个键值对（超过两个键值对，节点需要split，参考上面的规则），它们会被排序并按顺序存储在叶子节点中。对于一个节点的btree，我们假设节点的容量是两个键值对。当我们再插入一个时，我们要对叶子节点进行分裂，分裂后的两个节点各存储一半之前的键值对。两个分裂节点都成为内部节点，也成为新节点的子节点，新节点成为根节点。二层btree图中的内部节点（也是根节点）有一个key和两个指向子节点的指针（也就是两条线）。如果我们想找到一个小于或等于5的键，我们会在左子树中查找。如果搜索到的key大于5，则检查右子树。现在，准备插入一个新键“2”。首先，我们查找它将在哪个叶子中（如果它存在于树中），从而到达左叶子。该节点已满，因此拆分叶子节点并在父节点创建新条目。四节点的btree现在继续添加键，18和21。现在我们又要分裂了，但是父节点已经没有空间添加新的键值对了。内部节点没有空间。解决方法是将根节点拆分为两个内部节点，然后创建一个新的根节点作为两个内部节点的父节点。三级btree树只有在我们分裂根节点时深度才会增加。每个叶节点具有相同的深度和几乎相同数量的键值对，因此树可以是平衡的并且查找速度很快。在实现插入之前，我不会讨论从树中删除键。当我们实现这个数据结构时，每个节点对应一个页面。根节点将存在于page0中。节点内的子节点指针将简单地使用包含子节点的页码。
