关于golang:Radix压缩字典树的原理以及Go语言实现代码

Radix 树

Radix 树，即基数树，也称压缩字典树，是一种提供 key-value 存储查找的数据结构。radix tree 罕用于疾速查找的场景中，例如：redis 中存储 slot 对应的 key 信息、内核中应用 radix tree 治理数据结构、大多数 http 的 router 通过 radix 治理路由。Radix 树在 Trie Tree（字典树）的原理上优化过去的。因而在介绍 Radix 树的特点之首先简略介绍一下 Trie Tree。

Trie 树

Trie Tree，即字典树。Trie Tree 的原理是将每个 key 拆分成一个个字节，而后对应到每个分支上，分支所在的节点对应为从根节点到以后节点的拼接出的 key 的值。下图由四个字符串：haha、hehe、god、goto，造成的一个 Trie 树的示例：

利用上图中结构的 Trie Tree，咱们能够很不便的检索一个单词是否呈现在原来的字符串汇合中。例如，咱们检索单词：hehe，那么咱们从根节点开始，而后一一单词进行比照，路径结点：h-e-h-e，就定位到要检索的字符串了。从中能够看出，Trie Tree 查找效率是十分高的，达到了 O(K)，其中 K 是字符串的长度。

Radix 树特点

尽管 Trie Tree 具备比拟高的查问效率，然而从上图能够看到，有许多结点只有一个子结点。这种状况是不必要的，岂但影响了查问效率（减少了树的高度），次要是节约了存储空间。齐全能够将这些结点合并为一个结点，这就是 Radix 树的由来。Radix 树将只有一个子节点的两头节点将被压缩，使之具备更加正当的内存应用和查问的效率。下图是采纳 Radix 树后的示例：

与 hash 表的比照

• 查问效率
  Radix 树的插入、查问、删除操作的工夫复杂度都为 O(k)。hash 表的安查问效率：hash 函数计算效率 +O(1)，当然与若 hash 函数若选取不合理，则会造成抵触，会造成 hash 表的查问效率升高。总总体上来说两者查问性能根本相等（hash 函数的效率基本上等于 O(k)）。
• 空间效率
  从空间应用来说，hash 占优，因为 Radix 树的每个节点的节点负载较高，Radix 树的结点须要有指向子结点的指针。
• 其余方面
  hash 表的毛病有：数据量增长的状况下可能须要 rehash。Radix 树不会存在 rehash 的状况，然而若数据数据密集，则会造成 Radix 树进化为 Trie 树，会升高空间应用效率以及查问效率。
• 取舍倡议
  如果数据稠密，Radix 树能够更好的节俭空间，这种状况下应用 Radix 树会更佳。如果数据量小但数据密集，则倡议抉择 hash 表。

Radix 树的 Go 语言版本

本文应用 Go 语言来实现 Radix 树，目前代码曾经上传到 github 中，下载地址

在该代码中应用二叉树来实现 Radix 树，绝对与四叉树的版本，本版本在存储空间的使用率方面会更好一点，但会就义肯定的查问效率。
若谋求查问效率，请应用多叉树来实现。

应用二叉树来解决字符串时，将字符串看作 bit 数组，而后一一 bit 来比照两这个 bit 数组，将 bit 数组后面雷同的局部保留到父结点，
将两个 bit 数组的前面的局部别离保留到 left 子结点以及 right 子结点中。例如：

god:  0110-0111  0110-1111  0110-0100
goto: 0110-0111  0110-1111  0111-0100  0110-1111

从上例能够看到，二者在地 20 位处不相等，因而:

• 0110-0111 0110-1111 011：被划分到父节点。
• 0-0100：被划分到 left 子结点。
• 1-0100 0110-1111：被划分到 right 子结点。

定义

首先给出 Radix 树的定义：

type RaxNode struct {
    bit_len int
    bit_val []byte
    left     *RaxNode
    right     *RaxNode
    val interface{}}
type Radix struct {root [256]*RaxNode
}
func NewRaxNode() *RaxNode {nd := &RaxNode{}
    nd.bit_len = 0
    nd.bit_val = nil
    nd.left = nil
    nd.right = nil
    nd.val = nil
    return nd
}

将数据增加到 Radix 树

// 增加元素
func (this *Radix)Set(key string, val interface{}) {data := []byte(key)
    root := this.root[data[0]]
    if root == nil {
        // 没有根节点，则创立一个根节点
        root = NewRaxNode()
        root.val = val
        root.bit_val = make([]byte, len(data))
        copy(root.bit_val, data)
        root.bit_len = len(data) * 8
        this.root[data[0]] = root
        return
    } else if root.val == nil &&  root.left == nil && root.right == nil {
        // 只有一个根节点，并且是一个空的根节点，则间接赋值
        root.val = val
        root.bit_val = make([]byte, len(data))
        copy(root.bit_val, data)
        root.bit_len = len(data) * 8
        this.root[data[0]] = root
        return
    }

    cur := root
    blen := len(data) * 8
    for bpos := 0; bpos < blen && cur != nil; {bpos, cur = cur.pathSplit(data, bpos, val)
    }
}
func (this *RaxNode)pathSplit(key []byte, key_pos int, val interface{}) (int, *RaxNode) {// 与 path 对应的 key 数据(去掉曾经解决的公共字节)
    data := key[key_pos/8:]
    //key 以 bit 为单位长度（蕴含开始字节的字节内 bit 位的偏移量）bit_end_key := len(data) * 8
    //path 以 bit 为单位长度（蕴含开始字节的字节内 bit 位的偏移量）bit_end_path := key_pos % 8 + int(this.bit_len)
    // 以后的 bit 偏移量，须要越过开始字节的字节内 bit 位的偏移量
    bpos := key_pos % 8
    for ; bpos < bit_end_key && bpos < bit_end_path; {
        ci := bpos / 8
        byte_path := this.bit_val[ci]
        byte_data := data[ci]

        // 起始字节的外部偏移量
        beg := 0
        if ci == 0 {beg = key_pos % 8}
        // 终止字节的外部偏移量
        end := 8
        if  ci == bit_end_path / 8 {
            end = bit_end_path % 8
            if end == 0 {end = 8}
        }

        if beg != 0 || end != 8 {
            // 不残缺字节的比拟，若不等则跳出循环
            // 若相等，则增长 bpos，并持续比拟下一个字节
            num := GetPrefixBitLength2(byte_data, byte_path, beg, end)
            bpos += num
            if num < end - beg {break}
        } else if byte_data != byte_path {
            // 残缺字节比拟，num 为雷同的 bit 的个数，bpos 减少 num 后跳出循环
            num := GetPrefixBitLength2(byte_data, byte_path, 0, 8)
            bpos += num
            break
        } else {
            // 残缺字节比拟，相等，则持续比拟下一个字节
            bpos += 8
        }
    }

    // 以后字节的地位
    char_index := bpos / 8
    // 以后字节的 bit 偏移量
    bit_offset := bpos % 8
    // 残余的 path 长度
    bit_last_path := bit_end_path - bpos
    // 残余的 key 长度
    bit_last_data := bit_end_key - bpos

    //key 的数据有残余
    // 若 path 有子结点，则持续解决子结点
    // 若 path 没有子结点，则创立一个 key 子结点
    var nd_data *RaxNode = nil
    var bval_data byte
    if bit_last_data > 0 {
        // 若 path 有子结点，则退出本函数，并在子结点中进行解决
        byte_data := data[char_index]
        bval_data = GET_BIT(byte_data, bit_offset)
        if bit_last_path == 0 {
            if bval_data == 0 && this.left != nil {return key_pos + int(this.bit_len), this.left
            } else if bval_data == 1 && this.right != nil {return key_pos + int(this.bit_len), this.right
            }
        }

        // 为残余的 key 创立子结点
        nd_data = NewRaxNode()
        nd_data.left = nil
        nd_data.right = nil
        nd_data.val = val
        nd_data.bit_len = bit_last_data
        nd_data.bit_val = make([]byte, len(data[char_index:]))
        copy(nd_data.bit_val, data[char_index:])

        // 若 bit_offset!=0，阐明不是残缺字节，// 将字节决裂，并将字节中的非公共局部分离出来, 保留到子结点中
        if bit_offset != 0 {byte_tmp := CLEAR_BITS_LOW(byte_data, bit_offset)
            nd_data.bit_val[0] = byte_tmp
        }
    }

    //path 的数据有残余
    // 创立子节点：nd_path 结点
    // 并将数据离开，公共局部保留 this 结点，其余保留到 nd_path 结点
    var nd_path *RaxNode = nil
    var bval_path byte
    if bit_last_path > 0 {byte_path := this.bit_val[char_index]
        bval_path = GET_BIT(byte_path, bit_offset)

        // 为残余的 path 创立子结点
        nd_path = NewRaxNode()
        nd_path.left = this.left
        nd_path.right = this.right
        nd_path.val = this.val
        nd_path.bit_len = bit_last_path
        nd_path.bit_val = make([]byte, len(this.bit_val[char_index:]))
        copy(nd_path.bit_val, this.bit_val[char_index:])

        // 将 byte_path 字节中的非公共局部分离出来, 保留到子结点中
        if bit_offset != 0 {byte_tmp := CLEAR_BITS_LOW(byte_path, bit_offset)
            nd_path.bit_val[0] = byte_tmp
        }

        // 批改以后结点，作为 nd_path 结点、nd_data 结点的父结点
        // 多申请一个子节，用于存储可能呈现的不残缺字节
        bit_val_old := this.bit_val
        this.left = nil
        this.right = nil
        this.val = nil
        this.bit_len = this.bit_len - bit_last_path //=bpos - (key_pos % 8)
        this.bit_val = make([]byte, len(bit_val_old[0:char_index])+1)
        copy(this.bit_val, bit_val_old[0:char_index])
        this.bit_val = this.bit_val[0:len(this.bit_val)-1]

        // 将 byte_path 字节中的公共局部分离出来, 保留到父结点
        if bit_offset != 0 {byte_tmp := CLEAR_BITS_HIGH(byte_path, 8-bit_offset)
            this.bit_val = append(this.bit_val, byte_tmp)
        }
    }

    // 若 path 蕴含 key，则将 val 赋值给 this 结点
    if bit_last_data == 0 {this.val = val}
    if nd_data != nil {
        if bval_data == 0 {this.left  = nd_data} else {this.right = nd_data}
    }
    if nd_path != nil {
        if bval_path == 0 {this.left  = nd_path} else {this.right = nd_path}
    }
    return len(key) * 8, nil
}

Radix 树的查问

func (this *Radix)Get(key string) interface{}{data := []byte(key)
    blen := len(data) * 8
    cur := this.root[data[0]]

    var iseq bool
    for bpos := 0; bpos < blen && cur != nil; {iseq, bpos = cur.pathCompare(data, bpos)
        if iseq == false {return nil}
        if bpos >= blen {return cur.val}

        byte_data := data[bpos/8]
        bit_pos := GET_BIT(byte_data, bpos%8)
        if bit_pos == 0 {cur = cur.left} else {cur = cur.right}
    }

    return nil
}
func (this *RaxNode)pathCompare(data []byte, bbeg int) (bool, int) {bend := bbeg + int(this.bit_len)
    if bend > len(data) * 8 {return false, len(data) * 8
    }

    // 起始和终止字节的地位
    cbeg := bbeg / 8; cend := bend / 8
    // 起始和终止字节的偏移量
    obeg := bbeg % 8; oend := bend % 8
    for bb := bbeg; bb < bend; {
        // 获取两个数组的以后字节地位
        dci := bb / 8
        nci := dci - cbeg

        // 获取数据的以后字节以及循环步长
        step := 8
        byte_data := data[dci]
        if dci == cbeg && obeg > 0 {
            // 清零不残缺字节的低位
            byte_data = CLEAR_BITS_LOW(byte_data, obeg)
            step -= obeg
        }
        if dci == cend && oend > 0 {
            // 清零不残缺字节的高位
            byte_data = CLEAR_BITS_HIGH(byte_data, 8-oend)
            step -= 8-oend
        }

        // 获取结点的以后字节，并与数据的以后字节比拟
        byte_node := this.bit_val[nci]
        if byte_data != byte_node {return false, len(data)*8
        }

        bb += step
    }

    return true, bend
}

Radix 树的删除

func (this *Radix)Delete(key string) {data := []byte(key)
    blen := len(data) * 8
    cur := this.root[data[0]]

    var iseq bool
    var parent *RaxNode = nil
    for bpos := 0; bpos < blen && cur != nil; {iseq, bpos = cur.pathCompare(data, bpos)
        if iseq == false {return}

        if bpos >= blen {
            // 将以后结点批改为空结点
            // 若 parent 是根节点，不能删除
            cur.val = nil
            if parent == nil {return}

            // 以后结点是叶子结点，先将以后结点删除，并将以后结点指向父结点
            if cur.left == nil && cur.right == nil {
                if parent.left == cur {parent.left = nil} else if parent.right == cur {parent.right = nil}
                bpos -= int(cur.bit_len)
                cur = parent
            }

            // 尝试将以后结点与以后结点的子节点进行合并
            cur.pathMerge(bpos)
            return
        }

        byte_data := data[bpos/8]
        bit_pos := GET_BIT(byte_data, bpos%8)
        if bit_pos == 0 {
            parent = cur
            cur = cur.left
        } else {
            parent = cur
            cur = cur.right
        }
    }
}
func (this *RaxNode)pathMerge(bpos int) bool {
    // 若以后结点存在值，则不能合并
    if this.val != nil {return false}

    // 若以后结点有 2 个子结点，则不能合并
    if this.left != nil && this.right != nil {return false}

    // 若以后结点没有子结点，则不能合并
    if this.left != nil && this.right != nil {return false}

    // 获取以后结点的子结点
    child := this.left
    if this.right != nil {child = this.right}

    // 判断以后结点最初一个字节是否是残缺的字节
    // 若不是残缺字节，须要与子结点的第一个字节进行合并
    if bpos % 8 != 0 {char_len := len(this.bit_val)
        char_last := this.bit_val[char_len-1]
        char_0000 := child.bit_val[0]
        child.bit_val = child.bit_val[1:]
        this.bit_val[char_len-1] = char_last | char_0000
    }

    // 合并以后结点以及子结点
    this.val = child.val
    this.bit_val = append(this.bit_val, child.bit_val...)
    this.bit_len += child.bit_len
    this.left = child.left
    this.right = child.right

    return true
}