algorithm-study/6_tree/btree/note.md at master · 981377660LMT/algorithm-study

以下是一份关于 btree 包中这段 Go B-Tree 泛型实现（BTreeG[T]） 的详细解析。代码相对完整且较为复杂，融合了 Copy-On-Write、PathHint（路径提示加速）、锁（可选）、bulk load、iter 等众多机制。为方便理解，本解读将分为若干部分，并对核心结构与关键函数做逐步阐述。

整体概览
数据结构：BTreeG[T], node[T] 等
核心成员与初始化
查找相关：bsearch / find / hintsearch
路径提示(PathHint)
插入/删除
Copy-On-Write 机制
锁相关
迭代器（IterG[T]）
其他操作：如 GetAt, DeleteAt, Load, PopMin/PopMax, Min/Max…

1. 整体概览

BTreeG[T] 是一个支持泛型的 B-Tree 数据结构，提供了如下特性：

常规 B-Tree：插入、删除、查找、迭代等操作，仍保持 O(log N)。
Copy-On-Write (COW)：当克隆 ( Copy() / IsoCopy() ) 一棵树时，并不会复制所有节点，而是在写操作时“懒复制”节点，节省内存与时间。
Path Hints：针对多次访问相近 key 的情况，可以传入 PathHint 来跳过二分搜索的一部分操作，提升速度。
并发安全：可配置是否使用 sync.RWMutex（locks = true 时启用），从而在多协程下使用。

核心类型大致包括：

BTreeG[T]：表示一棵泛型 B-Tree
node[T]：树的节点，存储 items 切片和可选的 children 数组
PathHint：存储路径提示，用于加速查找
Options：配置项，比如 Degree、NoLocks
IterG[T]：迭代器

2. 数据结构

2.1 `BTreeG[T]`

type BTreeG[T any] struct {
    isoid        uint64        // 树的“隔离ID”，用于COW判断
    mu           *sync.RWMutex // 读写锁
    root         *node[T]      // 根节点
    count        int           // 元素总数
    locks        bool          // 是否启用锁
    copyItems    bool          // 是否需要在插入/复制时对 items 做深拷贝
    isoCopyItems bool          // 是否需要特殊的 IsoCopy
    less         func(a, b T) bool
    empty        T             // 零值
    max          int           // 最大可容纳的items (2*degree - 1)
    min          int           // 最少要求的items
}

isoid：通过 newIsoID() 生成，用于区分不同“副本”之间的节点归属（Copy-On-Write 的核心）。
root：指向根节点，若为空表示树空。
count：当前树中所有元素的数量。
max, min：与 B-Tree 的最小度数 (degree) 相关，决定每个节点最多/最少能存储的元素数。
less(a, b T) bool：比较函数，用来在插入/查找时做排序判定。

2.2 `node[T]`

type node[T any] struct {
    isoid    uint64    // 节点所属的隔离ID, 和BTreeG[T].isoid对应
    count    int       // 该节点(含子节点)下所有元素的数量
    items    []T       // 节点内存放的元素(有序)
    children *[]*node[T] // 指向子节点的列表(如果是内部节点)
}

leaf()：若 children == nil，表示叶子节点。

2.3 `PathHint`

type PathHint struct {
    used [8]bool   // 记录深度小于8的节点是否已经使用hint
    path [8]uint8  // 存储每层的索引位置
}

最多记录 8 层深度（对绝大部分实际 B-Tree 已足够）。
在搜索时可优先使用 hint 里的 index，而不是做二分。

3. 核心成员与初始化

3.1 New / Options

func NewBTreeG[T any](less func(a, b T) bool) *BTreeG[T] {
    return NewBTreeGOptions(less, Options{})
}
func NewBTreeGOptions[T any](less func(a, b T) bool, opts Options) *BTreeG[T] {
    tr := new(BTreeG[T])
    tr.isoid = newIsoID()
    tr.mu = new(sync.RWMutex)
    tr.locks = !opts.NoLocks
    tr.less = less
    tr.init(opts.Degree)
    return tr
}
func (tr *BTreeG[T]) init(degree int) {
    if tr.min != 0 {
        return
    }
    tr.min, tr.max = degreeToMinMax(degree) // 转换degree到min/max
    // 检查 empty 这个零值是否是 copier[T]/isoCopier[T] (可选)
    ...
}

degreeToMinMax(deg int) (min, max int)：度数 -> 最少/最多存储的元素数量。
tr.init(0) 在没有指定 degree 时会默认 32。

3.2 `newNode(leaf bool) *node[T]`

func (tr *BTreeG[T]) newNode(leaf bool) *node[T] {
    n := &node[T]{isoid: tr.isoid}
    if !leaf {
        n.children = new([]*node[T])
    }
    return n
}

分配一个节点，若不是叶子，创建 children 切片。
isoid 与 B-Tree 相同，用于判断是否需要 copy-on-write。

4. 查找相关：`bsearch` / `find` / `hintsearch`

4.1 `bsearch`

func (tr *BTreeG[T]) bsearch(n *node[T], key T) (index int, found bool) {
    low, high := 0, len(n.items)
    for low < high {
        mid := (low + high) / 2
        if !tr.less(key, n.items[mid]) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if low > 0 && !tr.less(n.items[low-1], key) {
        return low - 1, true
    }
    return low, false
}

标准的二分搜索，用 tr.less(key, n.items[mid]) 做比较。
如果最终 low > 0 && !less(n.items[low-1], key) 说明 n.items[low-1] == key，返回 (low-1, true)。

4.2 `find(n, key, hint, depth)`

如果没有 hint，直接调用 bsearch。
如果传了 hint，则进入 hintsearch 优先尝试 hint 中的索引，再做局部二分，最后更新 hint。

4.3 `hintsearch`

func (tr *BTreeG[T]) hintsearch(n *node[T], key T, hint *PathHint, depth int) (index int, found bool) {
    // 如果hint已记录本层路径, 尝试 index = hint.path[depth] 处做对比
    // 若不匹配, 则在局部 [low, high] 范围做二分
    // ...
    // 最终返回 (index, found)
    // 并更新 hint.path[depth] = pathIndex
}

可以减少一次完整二分，从而加速若多次访问相邻 key。

5. 路径提示 (`PathHint`)

type PathHint struct {
    used [8]bool
    path [8]uint8
}

在多次操作（例如 SetHint, GetHint, DeleteHint）中传入同一个 PathHint。
树会更新这条提示，使其对下次访问更加精准。
如果出错了，依旧会 fallback 到二分搜索。

6. 插入 / 删除

6.1 `Set()` / `SetHint()`

func (tr *BTreeG[T]) SetHint(item T, hint *PathHint) (prev T, replaced bool) {
    if tr.locks { tr.mu.Lock(); defer tr.mu.Unlock() }
    return tr.setHint(item, hint)
}
func (tr *BTreeG[T]) setHint(item T, hint *PathHint) (prev T, replaced bool) {
    if tr.root == nil {
        // 树为空，初始化root
        ...
    }
    prev, replaced, split := tr.nodeSet(&tr.root, item, hint, 0)
    if split {
        // root节点满了, 需要分裂root
        left := tr.isoLoad(&tr.root, true)
        right, median := tr.nodeSplit(left)
        tr.root = tr.newNode(false)
        *tr.root.children = []*node[T]{left, right}
        tr.root.items = []T{median}
        tr.root.updateCount()
        // 再次调用setHint保证插入真正落到分裂后的合适节点
        return tr.setHint(item, hint)
    }
    if replaced {
        return prev, true
    }
    tr.count++
    return tr.empty, false
}

nodeSet：递归插入到节点 n 中，如果 n 需要分裂就返回 split = true。
如果最终 root 也 split 了，就创建一个新的根节点，把 left、right 分裂结果挂上。

6.2 `nodeSet`

func (tr *BTreeG[T]) nodeSet(cn **node[T], item T, hint *PathHint, depth int) (
    prev T, replaced bool, split bool,
) {
    // 1. copy-on-write if needed
    if (*cn).isoid != tr.isoid {
        *cn = tr.copy(*cn)
    }
    n := *cn
    // 2. 查找插入位置 i
    i, found := ...
    if found {
        // 替换旧值
        prev = n.items[i]
        n.items[i] = item
        return prev, true, false
    }
    // 3. 若是叶子
    if n.leaf() {
        if len(n.items) == tr.max {
            return tr.empty, false, true // 需要split
        }
        // 直接插入
        n.items = append(n.items, tr.empty)
        copy(n.items[i+1:], n.items[i:])
        n.items[i] = item
        n.count++
        return tr.empty, false, false
    }
    // 4. 若非叶子，先递归到子节点
    prev, replaced, split = tr.nodeSet(&(*n.children)[i], item, hint, depth+1)
    if split {
        // 分裂子节点后再把“中间key”提到本节点
        if len(n.items) == tr.max {
            return tr.empty, false, true
        }
        right, median := tr.nodeSplit((*n.children)[i])
        ...
        // 递归继续插入到自身
        return tr.nodeSet(&n, item, hint, depth)
    }
    if !replaced {
        n.count++
    }
    return prev, replaced, false
}

6.3 `Delete()` / `DeleteHint()`

func (tr *BTreeG[T]) DeleteHint(key T, hint *PathHint) (T, bool) {
    if tr.lock(true) { defer tr.unlock(true) }
    return tr.deleteHint(key, hint)
}
func (tr *BTreeG[T]) deleteHint(key T, hint *PathHint) (T, bool) {
    if tr.root == nil { return tr.empty, false }
    prev, deleted := tr.delete(&tr.root, false, key, hint, 0)
    if !deleted { return tr.empty, false }
    if len(tr.root.items) == 0 && !tr.root.leaf() {
        tr.root = (*tr.root.children)[0]
    }
    tr.count--
    if tr.count == 0 {
        tr.root = nil
    }
    return prev, true
}

delete 会在节点找出 key 位置，若是叶子，则直接移除；若是内部节点，需要找前驱/后继替换，或者合并子节点（nodeRebalance）。
同样需要在子节点元素数低于 min 时做合并或向兄弟节点借元素。

7. Copy-On-Write 机制

7.1 `isoLoad` & `isoid`

func (tr *BTreeG[T]) isoLoad(cn **node[T], mut bool) *node[T] {
    if mut && (*cn).isoid != tr.isoid {
        *cn = tr.copy(*cn)
    }
    return *cn
}

在修改（mut == true）节点前，会检查节点 isoid 是否与当前树 isoid 一致，不一致时执行 tr.copy(*cn) 创建副本并赋予新的 isoid。
tr.copy(n *node[T]) *node[T] 做了一个浅层拷贝：复制 items，若 copyItems 或 isoCopyItems 为真，则对每个 item 调用 Copy() 或 IsoCopy()。

7.2 `IsoCopy()` / `Copy()`

func (tr *BTreeG[T]) Copy() *BTreeG[T] {
    return tr.IsoCopy()
}
func (tr *BTreeG[T]) IsoCopy() *BTreeG[T] {
    if tr.lock(true) { defer tr.unlock(true) }
    tr.isoid = newIsoID() // 改变自身isoid
    tr2 := new(BTreeG[T])
    *tr2 = *tr
    tr2.mu = new(sync.RWMutex)
    tr2.isoid = newIsoID() // 新树也给一个新的isoid
    return tr2
}

当调用 IsoCopy() 时，会先更新当前树的 isoid（防止后续操作也要写时复制），再复制整个 BTreeG 结构给 tr2，然后给 tr2 一个新 isoid。
两个树共享 root 节点指针，但 isoid 不同，后续修改会触发 copy-on-write。

8. 锁相关

locks 表示是否需要加锁。
lock(write bool) / unlock(write bool)：
- 如果 locks 为 true, 在写操作时加 mu.Lock(), 读操作加 mu.RLock()。

9. 迭代器 ( `IterG[T]` )

9.1 数据结构

type IterG[T any] struct {
    tr      *BTreeG[T]
    mut     bool
    locked  bool
    seeked  bool
    atstart bool
    atend   bool
    stack0  [4]iterStackItemG[T]
    stack   []iterStackItemG[T]
    item    T
}

type iterStackItemG[T any] struct {
    n *node[T]
    i int
}

维护一个栈，从根节点一路往下，记录访问过的节点和 index，用来支持 Next() / Prev() 操作。

9.2 使用方式

iter := tr.Iter() // 或 tr.IterMut()
defer iter.Release()

ok := iter.First()
for ok {
    item := iter.Item()
    ...
    ok = iter.Next()
}

Seek(key) / SeekHint(key, hint)：从 root 开始查找 key 并将位置记录到 stack 中。
Next()：
- 若是叶节点，就 i++，如果越界则回溯父节点；
- 若不是叶子，则进入下一子节点的最左分支。
Prev() 同理反方向。

10. 其他操作

GetAt(index) / DeleteAt(index)：支持按序号访问。通过 n.count 来定位是去哪个子节点，或命中 n.items[i]。
PopMin() / PopMax()：弹出最小/最大。
Load(item T)：bulk load 的一种方式，用于往末尾追加插入时做快速处理。
Walk() / Scan()：遍历整棵树，Walk是一次性批量传入回调的 slices；Scan一边调用 iter(item) 一边返回。
Min() / Max()：去最左/最右路径拿到最小/最大值。

总体小结

数据结构概念
- BTreeG[T] + node[T] 实现 B-Tree 基础；isoid + isoLoad + copy(...) 实现了 Copy-On-Write。
路径提示 (PathHint)
- 用于跳过常规二分搜索的一部分，若访问 key 分布相近，可大幅加速。
锁
- 通过 locks 开关决定是否用 sync.RWMutex，满足多协程访问需求。
插入/删除
- 标准 B-Tree 做法，节点满了就分裂 (split)，节点不足就合并 (rebalance)。
- 在插入/删除/修改时，若节点不属于当前 isoid，则执行 copy-on-write。
迭代器
- 保存从根到当前位置的节点索引栈 stack，实现 Next() / Prev()。
Copy-On-Write
- 核心在 isoLoad()，若 (*cn).isoid != tr.isoid 并且是写操作，会复制节点。
- IsoCopy() 使得整棵树复制仅仅是“新分配了一个 BTreeG 结构”，节点本身暂不复制，直至后续有写操作发生时复制节点。

这份代码融合了多种实用技巧，适合在读多写少或局部写、并发场景下使用。通过 PathHint、COW、锁、迭代器 等手段，提供了一个功能相当完善且高性能的泛型 B-Tree 实现。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

1. 整体概览

2. 数据结构

2.1 `BTreeG[T]`

2.2 `node[T]`

2.3 `PathHint`

3. 核心成员与初始化

3.1 New / Options

3.2 `newNode(leaf bool) *node[T]`

4. 查找相关：`bsearch` / `find` / `hintsearch`

4.1 `bsearch`

4.2 `find(n, key, hint, depth)`

4.3 `hintsearch`

5. 路径提示 (`PathHint`)

6. 插入 / 删除

6.1 `Set()` / `SetHint()`

6.2 `nodeSet`

6.3 `Delete()` / `DeleteHint()`

7. Copy-On-Write 机制

7.1 `isoLoad` & `isoid`

7.2 `IsoCopy()` / `Copy()`

8. 锁相关

9. 迭代器 ( `IterG[T]` )

9.1 数据结构

9.2 使用方式

10. 其他操作

总体小结

FilesExpand file tree

note.md

Latest commit

History

note.md

File metadata and controls

1. 整体概览

2. 数据结构

2.1 BTreeG[T]

2.2 node[T]

2.3 PathHint

3. 核心成员与初始化

3.1 New / Options

3.2 newNode(leaf bool) *node[T]

4. 查找相关：bsearch / find / hintsearch

4.1 bsearch

4.2 find(n, key, hint, depth)

4.3 hintsearch

5. 路径提示 (PathHint)

6. 插入 / 删除

6.1 Set() / SetHint()

6.2 nodeSet

6.3 Delete() / DeleteHint()

7. Copy-On-Write 机制

7.1 isoLoad & isoid

7.2 IsoCopy() / Copy()

8. 锁相关

9. 迭代器 ( IterG[T] )

9.1 数据结构

9.2 使用方式

10. 其他操作

总体小结

2.1 `BTreeG[T]`

2.2 `node[T]`

2.3 `PathHint`

3.2 `newNode(leaf bool) *node[T]`

4. 查找相关：`bsearch` / `find` / `hintsearch`

4.1 `bsearch`

4.2 `find(n, key, hint, depth)`

4.3 `hintsearch`

5. 路径提示 (`PathHint`)

6.1 `Set()` / `SetHint()`

6.2 `nodeSet`

6.3 `Delete()` / `DeleteHint()`

7.1 `isoLoad` & `isoid`

7.2 `IsoCopy()` / `Copy()`

9. 迭代器 ( `IterG[T]` )