The Practice

本章将在 Golang 中完成一棵不可变的 B 树。完成进程十分简单，因而很简单理解。

The Node Format

咱们的B树最终会耐久化到磁盘上，所以咱们需求先规划B树节点的传输格局。假如没有格局，咱们将不知道节点的巨细以及何时拆分节点。

一个 node 包括：

巨细固定的标头，包括节点类型（叶节点或内部节点）和键的数量。
指向子节点的指针列表(内部节点运用）。
指向每个键值对的偏移量列表。
打包好的 KV 对。

| type | nkeys |  pointers  |   offsets  | key-values
|  2B  |   2B  | nkeys * 8B | nkeys * 2B | ...

type：代表节点类型，这儿为了简单只有两种节点类型（内节点和叶子节点）
nkeys：代表页中一共有多少个 key
pointers：存储了一切 key 所在页的地址
offsets：存储了一切 key 在当前页中的偏移量
key-values：实践记载（仅在叶子节点生效）

这就是 KV 对的格局，长度后跟数据。

| klen | vlen | key | val |
|  2B  |  2B  | ... | ... |

为了简单起见，叶节点和内部节点都运用相同的格局。

Data Types

既然咱们最终要将 B 树转储到磁盘，为什么不运用字节数组作为咱们的内存数据结构呢？

type BNode struct {
    data []byte  // can be dumped to the disk
}
const (
    BNODE_NODE = 1 // internal nodes without values 内节点
    BNODE_LEAF = 2 // leaf nodes with values        叶子节点
)

并且咱们不能运用内存中的指针，指针是引用磁盘页的64位整数（也叫内存地址），而不是内存中的节点，咱们将添加一些回调来抽象这个方面，这样咱们的数据结构代码仍然是纯数据结构代码。

tpye BTree struct {
    // pointer ( a nonzero page number)
    root uint64
    // callbacks for managing on-disk pages
    get func(uint64) BNode // dereference a pointer
    new func(BNode) uint64 // allocate a new page
    del func(uint64)      // deallocate a page
}

页面巨细定义为 4K 字节，更大的页面巨细（如 8K 或 16K）也能够运用。

一个 uint64 的指针值仅有指向一个 BNode，即一个页

咱们还添加了一些对键和值的巨细的束缚。因而，具有单个 KV 对的节点一直能够放在单个页面上。假如您需求支撑更大的键或更大的值，则有必要为它们分配额定的页面，这会添加复杂性。

const HEADER = 4
const BTREE_PAGE_SIZE = 4096
const BTREE_MAX_KEY_SIZE = 1000
const BTREE_MAX_VAL_SIZE = 3000
func init() {
    node1max := HEADER   8   2   4   BTREE_MAX_KEY_SIZE   BTREE_MAX_VAL_SIZE 
    assert(node1max <= BTREE_PAGE_SIZE)
}

Build Your Own Database From Scratch~04 B-Tree

Decoding the B-tree Node

由于节点仅仅一个字节数组，因而咱们将添加一些辅助函数来访问其内容。

// header
func (node BNode) btype() uint16 {
    return binary.LittleEndian.Uint16(node.data)
}
func (node BNode) nkeys() uint16 {
    return binary.LittleEndian.Uint16(node.data[2:4])
}
func (nonde BNode) setHeader(btype uint16, nkeys uint16) {
    binary.LittleEndian.PutUint16(node.data[0:2], btype)
    binary.LittleEndian.PutUint16(node.data[2:4], nkeys)
}

// pointers
func (node BNode) getPtr(idx uint16) uint64 {
    assert(idx < node.nkeys())
    // 获取 idx 对应页的地址偏移量
    pos := HEADER   8 * idx
    return binary.LittleEndian.Uint64(node.data[pos:])
}
func (node BNode) setPtr(idx uint64, val uint64) {
    assert(idx < node.nkeys())
    pos := HEADER   idx * 8
    binary.LittleEndian.PutUint64(node.data[pos:], val)
}

有关偏移列表的一些详细信息：

该偏移量是相对于第一个 KV 对的方位而言的。
第一个 KV 对的偏移量一直为零，因而不存储在列表中。
咱们在偏移量列表中存储最终一个 KV 对结尾的偏移量，用来确认节点的巨细。

// offset list
func offsetPos(node BNode, idx uint16) uint16 {
    assert(1 <= idx && idx <= node.nkeys())
    // idx 在 offset list 中的偏移量
    return HEADER    8 * node.nkeys()   2 * (idx-1)
}
func (node BNode) getOffset(idx uint16) uint16 {
    if idx == 0 {
        return 0
    }
    // 获取 idx 对应节点的 kv 偏移量信息
    // 首先获取 idx 对应节点的在偏移量列表中的偏移量
    // 然后读取 2B 字节后回来 idx 对应的 KV 在数据部分的偏移量
    return binary.LittleEndian.Uint16(node.data[offsetPos(node, idx):])
}

// key-values
func (node BNode) kvPos(idx uint16) uint16 {
    assert(idx <= node.nkeys())
    // 相似与 golang map 定位 kv
    // HEADER   8 * node.nkeys()   2 * node.nkeys() 这儿是记载元信息部分
    // 记载元信息部分之后全部都是数据部分，而 getOffset 现已求出了 kv 在这部分的偏移量，把记载元信息部分长度 kv 在数据部分的偏移量就得到了：idx 这个 kv 对比较于整个页的起始方位的偏移量
    return HEADER   8 * node.nkeys()   2 * node.nkeys()   node.getOffset(idx)
}
func (node BNode) getKey(idx uint16) []byte {
    assert(idx < node.nkeys())
    // idx 对应 kv 对的起始偏移量（相对于数据部分起始方位来说）
    pos := node.kvPos(idx)
    // klen(2B)   vlen(2B)   key   value
    klen := binary.LittleEndian.Uint16(node.data[pos:])
    // node.data[pos 4:] （第一个 kv 的数据部分起始方位）读取 klen 长度
    return node.data[pos 4:][:klen]
}
func (node BNode) getVal(idx uint16) []byte {
    assert(idx < node.nkeys())
    pos := node.kvPos(idx)
    // klen(2B)   vlen(2B)   key   value
    klen := binary.LittleEndian.Uint16(node.data[pos 0:])
    vlen := binary.LittleEndian.Uint16(node.data[pos 2:])
    return node.data[pos 4 klen:][:vlen]
}

并确认节点的巨细。

// node size in bytes
func (node BNode) nbytes uint16 {
    // 调用 kvPos 的 idx = nkeys ，这相当于求最终一条 kv 比较于页开头的偏移量，那实践上就是求整个页的巨细
    return node.kvPos(node.nkeys())
}

The B-Tree Insertion

该代码被分解为小过程。

Step 1: Look Up the Key

要将键刺进叶节点，咱们需求在排序的 KV 列表中查找它的方位。

// returns the first kid node whose range intersects the key. (kid[i] <= key)
func nodeLookupLE(node BNode, key []byte) uint16 {
    nkeys := node.nkeys()
    found := uint16(0)
    // the first key is a copy from the parent node
    // thus it's always less than or equal to the key. 第一个 key 是父节点（根节点）的副本，因而它等于或者小于一切 key，这儿不在刺进逻辑中判别
    for i := uint16(1); i < nkeys; i   {
        cmp := bytes.Compare(node.getKey(i), key)
        if cmp <= 0 { // 在该页找到比 key 小的 key 列表中最大的 key
            found = i
        }
        if cmp >= 0 { // 因为 key 是从小到大摆放的，所以一旦找到一个 key >= target，那么之后一切的 key 都大于 target，因而能够直接退出循环了
            break
        }
    }
    return found
}

查找对叶节点和内部节点都有用。请注意，第一个键将被跳过比较，因为它现已与父节点比较过了。

Step 2: Update Leaf Nodes

查找到要刺进的方位后，咱们需求创建一个包括新键的节点副本。

// add a new key to a leaf node.
func leafInsert (new BNode, old BNode, idx uint16, key []byte, val []byte) {
    // 为新节点设置 header
    new.setHeader(BNODE_LEAF, old.nkeys() 1)
    // 刺进前半部分 KV 对
    nodeAppendRange(new, old, 0, 0, idx)
    // 刺进新的 KV 对
    nodeAppendKV(new, idx, 0, key, val)
    // 刺进后半部分 KV 对
    nodeAppendRange(new, old, idx 1, idx, old.nkeys()-idx)
}

nodeAppendRange 函数将旧节点中的键复制到新节点中。

// copy multiple KVs into the position
func nodeAppendRange(new, old BNode, dstNew uint64, srcOld uint16, n uint16) {
    // 越界判别
    assert(srcOld n <= old.nkeys())
    assert(dstNew n <= new.nkeys())
    if n == 0 {
        return
    }
    // pointers（设置最新的节点指针）
    for i := uint16(0); i < n; i   { // 更新 idx 列表中的节点指针
        // setPtr(idx, val)
        new.setPtr(dstNew i, old.getPtr(srcOld i))
    }
    // offsets（更新 offset）
    dstBegins := new.getOffset(dstNew)
    srcBegin := old.getOffset(srcOld)
    for i := uint16(1); i <= n; i   {
        offset := dstBegin   old.getOffset(srcOld i) - srcBegin
        new.setOffset(dstNew i, offset)
    }
    // kvs（数据搬移）
    begin := old.kvPos(srcOld)
    end := old.kvPos(srcOld   n)
    copy(new.data[new.kvPos(dstNew):], old.data[begin:end])
}

如图所示，假设以前页中存在 key=1、3、5、7 的四个 KV 对，现在刺进 key=6 的 KV 对，那么需求先将 1、3、5 的 KV 先刺进到新页中，然后将 key=6 的 KV 对刺进到之后，最终将 key=7 的 KV 对刺进到结尾，完成一次 newkey 的刺进操作。（从这儿咱们也能够看出为什么推荐运用 auto_increment 的主键索引了，那样就省略了 B 树割裂从头构造的开销了；只在页面不够用，才或许触发页的割裂操作）。

NodeAppendKV 函数将一个 KV 对复制到新节点。

// copy a KV into the position
func nodeAppendKV(new BNode, idx uint16, ptr uint64, key []byte, val []byte) {
    // ptrs
    new.setPtr(idx, ptr)
    // KVs
    pos := new.kvPos(idx)
    binary.LittleEndian.PutUint16(new.data[pos 0:], uint16(len(key)))
    binary.LittleEndian.PutUint16(new.data[pos 2:], uint16(len(val)))
    copy(new.data[pos 4:], key)
    copy(new.data[pos 4 uint16(len(key)):], val)
    // the offset of the next key
    new.setOffset(idx 1, new.getOffset(idx)   4   uint16((len(key) len(val))))
}

Step 3: Recursive Insertion

用于刺进键的主函数。

// 将 KV 刺进节点，成果或许会被分割成两个节点。调用者负责取消输入节点的分配，并分割和分配成果节点。
func treeInsert(tree *BTree, node BNode, key []byte, val []byte) BNode {
    // 成果节点。它允许大于1页，假如大于1页，将被拆分
    new := BNode{data: make([]byte, 2 * BTREE_PAGE_SIZE)}
    // where to insert the key?
    idx := nodeLookupLE(node, key)
    // 依据节点类型进行操作
    switch node.btype() {
        case BNODE_LEAF: // 或许是更新或者刺进操作
            if bytes.Equal(key, node.getKey(idx)) {
                // found the key, update it
                leafUpdate(new, node, key, val)
            } else {
                // insert it after the position
                leafInsert(new, node, idx 1, key, val)
            }
       case BNODE_NODE:
           // internal node, insert it to a kid node.
           nodeInsert(tree, new, node, idx, key, val)
       default:
           panic("bad node")
    }
    return new
}

leafUpdate 函数与 leafInsert 函数相似。

Step 4: Handle Internal Nodes

现在是处理内部节点的代码。

// KV insertion to an internal node
func nodeInsert(tree *BTree, new BNode, node BNode, idx uint16, key []byte, val []byte) {
    // get and deallocate the kid node
    kptr := node.getPtr(idx)
    knode := tree.get(kptr)
    tree.del(kptr)
    // 递归刺进进 kid node
    knode = treeInsert(tree, knode, key, val)
    // split the result
    nsplit, splited := nodeSplit3(knode)
    // update the kid links
    nodeReplaceKidN(tree, new, node, idx, splited[:nsplit]...)
}

Step 5: Split Big Nodes

将键刺进节点会添加其巨细，导致其超出页面巨细。在这种情况下，节点被分割成多个更小的节点。

允许的最大键巨细和值巨细仅保证单个 KV 对一直适合一页。在最坏的情况下，胖节点被分成3个节点（中间有一个大的 KV 对）。

// split a bigger-than-allowed node into two.
// the second node always fits on a page.
func nodeSplit2(left BNode, right BNode, old BNode) {
    // code omitted...
}
// split a node if it's too big. the results are 1~3 nodes.
func nodeSplit3(old BNode) (uint16, [3]BNode) {
    if old.nbytes() <= BTREE_PAGE_SIZE {
        old.data = old.data[:BTREE_PAGE_SIZE]
        return 1, [3]BNode{old}
    }
    left := BNode{make([]byte, 2*BTREE_PAGE_SIZE)} // might be split later
    right := BNode{make([]byte, BTREE_PAGE_SIZE)}
    nodeSplit2(left, right, old)
    if left.nbytes() <= BTREE_PAGE_SIZE {
        left.data = left.data[:BTREE_PAGE_SIZE]
        return 2, [3]BNode{left, right}
    }
    // the left node is still too large
    leftleft := BNode{make([]byte, BTREE_PAGE_SIZE)}
    middle := BNode{make([]byte, BTREE_PAGE_SIZE)}
    nodeSplit2(leftleft, middle, left)
    assert(leftleft.nbytes() <= BTREE_PAGE_SIZE)
    return 3, [3]BNode{leftleft, middle, right}
}

Step 6: Update Internal Nodes

将键刺进节点或许会发生 1、2 或 3 个节点。父节点有必要相应地更新本身。更新内部节点的代码与更新叶节点的代码相似。

// replace a link with multiple links
func nodeReplaceKidN(
    tree *BTree, new BNode, old BNode, idx uint16,
    kids ...BNode,
) {
    inc := uint16(len(kids))
    new.setHeader(BNODE_NODE, old.nkeys() inc-1)
    nodeAppendRange(new, old, 0, 0, idx)
    for i, node := range kids {
        nodeAppendKV(new, idx uint16(i), tree.new(node), node.getKey(0), nil)
    }
    nodeAppendRange(new, old, idx inc, idx 1, old.nkeys()-(idx 1))
}

咱们现已完成了 B 树的刺进，删去以及其他代码将在下一章介绍。

Build Your Own Database From Scratch~04 B-Tree

The Practice

The Node Format

Data Types

Decoding the B-tree Node

The B-Tree Insertion

Step 1: Look Up the Key

Step 2: Update Leaf Nodes

Step 3: Recursive Insertion

Step 4: Handle Internal Nodes

Step 5: Split Big Nodes

Step 6: Update Internal Nodes

相关文章

关于ChatGPT，我们请小红书技术人和NLP专家聊聊原理和潜力

苹果 CEO 库克在找接班人；大英图书馆确认被勒索软件攻击丨 RTE 开发者日报 Vol.90

（译）CSS实现高度从0到auto的过度动画

生存or毁灭？QQ空间150万行代码的涅槃重生

作者信息