基数树就是一种简单有效的分级索引结构，每层索引为键值的一个片段。
type node struct {
kids [Radix]unsafe.Pointer
}
func branch(key uint, depth uint) uint {
return (key >> (bitWidth - (depth+1)*Step)) & Mask
}基数树的操作比较简单，删除时注意级联处理就好。
func (m *Map) Remove(key uint) bool {
var path [Depth]*node
path[0] = &m.root
for i := uint(0); i < Depth-1; i++ {
path[i+1] = (*node)(path[i].kids[branch(key, i)])
if path[i+1] == nil { return false }
}
idx := key & Mask
if path[Depth-1].kids[idx] == nil { return false }
path[Depth-1].kids[idx] = nil
for i := Depth - 1; i != 0; i-- {
j := uint(0)
for j < Radix && path[i].kids[j] == nil { j++ }
if j == Radix { //全空
path[i-1].kids[branch(key, i-1)] = nil
} }
return true
}
字典树又称前缀树，是一种针对序列的索引结构。字典树的基本原理和基数树一样，不过由于序列长度并不固定，情况要更加复杂一些。另一方面，我们通常希望数据单元是有意义的片段（不宜小于一字节），导致节点的后继可能较多，故如何获得较好的空间利用率也是一项挑战。字典树节点的结构有多种，各有千秋，而这里介绍的一种分离指针数组结构则兼顾了便捷与效能。
type node struct {
data [segCap]byte //保存若干数据单元
mark uint8 //高位一bit表示是否实体，低位表示段长
kids []*node
}字典树的插入相对容易，注意处理分裂即可。
func (t *Trie) insert(key string) bool {
unit, skip := &t.root, uint8(0)
unit.compact() //在查询之前尝试节缩
brk := 0
for sz := unit.mark & 0x7f; len(key) > int(sz); sz = unit.mark & 0x7f {
brk = unit.diff(key, skip, sz)
if brk >= 0 { goto Lsplit }
skip = 1
key = key[sz:]
pos := search(unit.kids, key[0])
if pos >= len(unit.kids) || unit.kids[pos].data[0] != key[0] {
unit.kids = array.InsertTo(unit.kids, pos, createTail(key))
return true //在关节点增加分支
}
unit = unit.kids[pos]
unit.compact() //在查询之前尝试节缩
}
brk = unit.diff(key, skip, uint8(len(key)))
if brk < 0 {
if len(key) == int(unit.mark&0x7f) { //停在关节点，直接打标
done := (unit.mark & 0x80) == 0
unit.mark |= 0x80
return done
} else { //单分裂
unit.kids = []*node{unit.split(len(key))}
unit.mark |= 0x80
return true
} }
Lsplit: //双分裂
kid1 := createTail(key[brk:])
kid2 := unit.split(brk)
if kid1.data[0] > kid2.data[0] {
kid1, kid2 = kid2, kid1
}
unit.kids = []*node{kid1, kid2}
return true
}而删除则要考虑删除非共享序列片段。
func (t *Trie) remove(key string) bool {
knot, branch := (*node)(nil), -1 //追踪删除关节
unit, skip := &t.root, uint8(0)
unit.compact()
for sz := unit.mark & 0x7f; len(key) > int(sz); sz = unit.mark & 0x7f {
if (unit.mark&0x80) != 0 || len(unit.kids) > 1 {
knot = unit
}
if unit.diff(key, skip, sz) >= 0 { return false }
skip = 1
key = key[sz:]
pos := search(unit.kids, key[0])
if pos >= len(unit.kids) || unit.kids[pos].data[0] != key[0] {
return false
}
if knot == unit { branch = pos }
unit = unit.kids[pos]
unit.compact()
}
if (len(key)|0x80) == int(unit.mark) &&
unit.diff(key, skip, unit.mark&0x7f) < 0 {
if len(unit.kids) == 0 && knot != nil { //删除非共享序列片段
knot.kids = array.EraseFrom(knot.kids, branch, true)
} else {
unit.mark &= 0x7f
}
return true
}
return false
}