sqlite - B 树的节点使用哪种数据结构？

Question

根据 Knuth 的定义，m 阶 B 树（每个节点的最大子节点数）是一棵满足以下性质的树：

(1) 每个节点最多有 m 个子节点。

(2) 每个节点（根节点除外）至少有 ⌈m⁄2⌉ 个子节点。

(3) 如果根不是叶节点，则根至少有两个孩子。

(4) 具有 k 个子节点的非叶节点包含 k-1 个键。

(5) 所有叶子都出现在同一层次，并携带信息。

资料来源：维基百科

B 树的一些可视化如下所示：

从这个可视化中，我认为每个节点都有一个数组数据结构（或至少类似的东西）。

其他看起来像这样：

这看起来更像是一个类似列表的数据结构。

所以我的问题是：

B树使用哪种数据结构？

我的算法类中的使用示例是数据库和文件系统。有人知道SQLite如何实现 B-tree 节点吗？还是ext3？或者任何其他（众所周知的）现实世界的例子？

Answer 1

B-Tree 本身就是数据结构（也是一个索引结构）。这是一个伪代码示例（没有需要的方法和一些需要的定义，这是一个很好的 excersize！）：

节点的主体：

class BNode
{
    int keys[];
    BNode children[];

    public BNode() {}

    public BNode() {}

    public int getValue(int key) {}

    public BNode getChildren(int key) {}
}

B树的主体：

class BTree
{
    BNode root;

    BTree()
    {
        root = new BNode(null);
    }

    BNode search(int key) {}

    void insert(int key) {}

    void delete(int key) {}
}

---

在现实世界中：

这是用于索引数据库的 PostgreSQL的 B-Tree 实现。