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

Radix压缩字典树的原理以及Go语言实现代码Radix 树 Radix 树 即基数树 也称压缩字典树 是一种提供 key value 存储查找的数据结构 radix tree 常用于快速查找的场景中 例如 redis 中存储 slot 对应的 key 信息 内核中使用 radix tree 管理数据结构 大多数 http 的 router 通过 radix 管理路由 Radix 树在 Trie

大家好,我是讯享网,很高兴认识大家。

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中,下载地址

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 } 
小讯
上一篇 2025-01-24 10:35
下一篇 2025-03-07 18:50

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82549.html