Skip to content

Latest commit

 

History

History
221 lines (158 loc) · 8.73 KB

review.md

File metadata and controls

221 lines (158 loc) · 8.73 KB

在这份代码中，ART（Adaptive Radix Tree，自适应基数树）本身是一种前缀树（Radix Tree）在节点容量和内存利用上的优化版本。整个实现里，有很多值得学习的设计思路和技巧，这里总结几个主要的“技巧”或“思路”：

1. 统一的节点封装：nodeRef + kind

在传统的面向对象或其他语言中，如果想表示“多种类型的节点”，通常可以用继承或union来实现。然而在 Go 里没有继承也没有 union，于是作者利用 nodeRef + unsafe.Pointer + kind 完成了“多态节点”的编程模型：

type nodeRef struct {
    ref  unsafe.Pointer
    kind Kind
}
  • kind: 表示节点的类型（Leaf、Node4、Node16、Node48、Node256）。
  • ref: 通过 unsafe.Pointer 来承载各个类型的指针。

这样就把“各种内部节点实现”和“叶子节点实现”都能放在同一个指针上，并通过 kind 来区分实际类型。例如：

// 根据 kind 不同来强制转换：
func (nr *nodeRef) node4() *node4 {
    return (*node4)(nr.ref)
}
func (nr *nodeRef) node16() *node16 {
    return (*node16)(nr.ref)
}
// ...

优势：

  1. 减少类型断言次数：传统做法要判断“是不是 *node4” / “是不是 *node16” 等，写很多 switch v := nr.(type) {...} 的重复逻辑。这里通过 kind 做一次 switch 或调用 nr.node4() 这种简便方法即可。
  2. 无缝存储“多态”节点：只要赋值 nr.ref = unsafe.Pointer(...) 即可，而不用引入多层接口或复杂结构。

需要注意的地方：

  • unsafe.Pointer 本质上跳过了 Go 的类型安全检查，带来一定风险。一般需要仔细确保“转回去”的类型是对的。
  • 代码里用到的 //#nosec:G103 是为了告诉 lint 工具：这是一个确认过的用法，并非滥用 unsafe。

2. 自适应节点容量：node4/node16/node48/node256

自适应基数树的“自适应”主要体现在：当分支数量不足时，就用小容量节点；当分支增多时，就自动“grow”，变成更大容量节点；删除后分支变少时，就“shrink” 成更小容量节点。这种设计带来：

  • 当分支少时，用较小的结构（如 node4）可以减少内存开销；
  • 当分支多时，用大结构（如 node256）可以保证在查找/插入时能快速通过字符索引到子节点。

在实现里，这几种节点都有着近似的“骨架”，只是在如何存子节点上做了区别：

// node4
type node4 struct {
    node
    children [node4Max + 1]*nodeRef
    keys     [node4Max]byte
    present  [node4Max]byte
}

// node16
type node16 struct {
    node
    children [node16Max + 1]*nodeRef
    keys     [node16Max]byte
    present  present16
}

// node48
type node48 struct {
    node
    children [node48Max + 1]*nodeRef
    keys     [node256Max]byte
    present  present48
}

// node256
type node256 struct {
    node
    children [node256Max + 1]*nodeRef
}
  • node4：只有一个很短的 keys 数组和对应的 present 标志位；
  • node16：采用一个 16 位的位图 (present16)；
  • node48：则为每个字符分配一个 byte 索引；
  • node256：直接 256 大小的数组，一次性索引。

设计技巧：抽象分层 + 分配策略

作者将所有节点类型内嵌了相同的 node 结构，封装了公共字段（如 prefix、prefixLen 等），然后各节点再根据容量需求“各自存储子节点指针”。整个过程使用Grow / Shrink接口统一把节点进行大小调整，避免在各处散落繁琐的类型转换逻辑。

3. 核心操作都写成“接口”+“实现”

代码里有大量接口，比如：

type nodeLeafer interface {
    minimum() *leaf
    maximum() *leaf
}

type nodeOperations interface {
    addChild(kc keyChar, child *nodeRef)
    deleteChild(kc keyChar) int
}

type nodeSizeManager interface {
    hasCapacityForChild() bool
    grow() *nodeRef
    isReadyToShrink() bool
    shrink() *nodeRef
}

type nodeChildren interface {
    childAt(idx int) **nodeRef
    allChildren() []*nodeRef
}

type nodeKeyIndexer interface {
    index(kc keyChar) int
}

然后通过组合（embedding），让“具体的节点结构”如 *node4、*node16 实现这些接口。这种做法让代码高度模块化：

  • nodeOperations 只管“增删子节点”这一功能；
  • nodeSizeManager 只管“是否需要 grow/shrink，如何 grow/shrink”；
  • nodeLeafer 只管“从当前子树找最小/最大叶子”。

这样如果你只想改“当 node4 满时如何转成 node16”，就改 grow() 实现即可，不会影响其他逻辑。

4. 前缀压缩：prefixLen + prefix

自适应基数树为了在搜索时减少层数，会在内部节点存储一段公共前缀，如：

type node struct {
    prefix      prefix // prefix是 [maxPrefixLen]byte 的定长数组
    prefixLen   uint16
    childrenLen uint16
}
  • prefixLen 表示当前实际有多长的前缀，共用在下层所有 key 上；
  • prefix 存储了真实的前缀内容，但只存储到 maxPrefixLen（可配置，比如 10）。

搜索或插入时，先把这段 prefix 比对完，若全部相同，再往下找子节点；若中途不匹配，就进行 “split” 分裂。

设计思路：

  • 普通基数树每走一层只对比一个字符，而 ART 先在“prefix”上批量对比若干字符，加速了分支比较；
  • 同时需要一个 matchDeep 等函数，在插入/删除时计算出公共前缀长度，对后续节点做分裂或合并。

5. 版本号 version 控制并发修改

在迭代器 Iterator 时，如果树被其他地方“结构性修改”，理论上迭代逻辑可能出现错乱或并发安全问题。为了解决这个，作者在 tree 里放了一个 version：

type tree struct {
    version int
    ...
}
  • 每次对树做 插入 / 删除 等结构变更操作，就 tr.version++；
  • 迭代器在创建时会记下 it.version = tree.version；
  • 如果迭代过程中 tree.version != it.version，则抛出 ErrConcurrentModification 错误。

这是一种简单高效的“Fail-Fast”并发迭代检测技巧。

6. 递归 + 分段函数

在操作树的增删查时，代码采用了 “外层做前缀匹配 + 找子节点，内层再做递归处理” 的套路，写成若干小函数：

  • insertRecursively(...) / deleteRecursively(...) / handleLeafInsertion(...) / splitLeaf(...) ...
  • 每个函数只处理一种场景，然后递归深入到下一层。

这种“分段函数 + 递归”避免了一个超长的大函数，也让每个函数的逻辑更加聚焦，易读易维护。

7. 可视化 Debug 工具（DumpNode / TreeStringer）

最后一大段代码就是如何把整个树打印为一个漂亮的层级结构，里面也有很多技巧：

  • 维护一个 nodeRegistry 给节点分配 ID，帮助识别节点（即使指针地址不同，逻辑上仍然是同一个 key）。
  • 采用了类似“ASCII 树”风格去打印前缀、child 数组、叶子 key/value 等关键信息。
  • 用**选项模式（Option）**让用户可以指定要打印的格式，比如： 
    WithRefFormatter(RefAddrFormatter) // 只显示地址
WithRefFormatter(RefShortFormatter) // 只显示 #id
    这样可快速调整调试输出。

虽然这部分和树的核心逻辑无关，但是对于理解数据结构或做单元测试非常有帮助。好的调试/可视化工具往往能显著提高开发效率和可维护性。

总结

这份代码实现了一个功能完备的自适应基数树，核心的设计技巧包括：

  1. “多态节点”封装：nodeRef + kind + unsafe.Pointer
  2. 分层接口：nodeOperations / nodeSizeManager 等，精细拆分每个节点行为
  3. 自适应分支：node4 / node16 / node48 / node256，+ Grow / Shrink 动态转换
  4. 前缀压缩：在内部节点中存储 prefix + prefixLen 提升查找效率
  5. 版本号版本控制：Fail-Fast 并发检测
  6. 递归 + 分段函数：使得代码结构清晰，易读易维护
  7. 调试 & 可视化：DumpNode / TreeStringer 提供人性化树形输出

这些技巧不只适用于 ART，也可以迁移到其他需要“多种节点结构”的数据结构中，或者在做复杂结构的遍历、调试、并发检测时都能借鉴，体现了作者在 Go 语言和数据结构实现上的思考与经验。