关于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
}