精华内容
下载资源
问答
  • 数据结构基数树
    2021-08-19 16:27:09

    一、背景

        基数树在前面已经讲过了,将一个key划分成多段,每段的取值范围作为树的一层划分节点的基准,中间节点和叶子节点都存很多指针,中间节点的指针指向孩子节点,叶子节点的指针指向具体的value。

        从上述描述可知,基数树的树高取决于key长。

        问题:使用基数树的场景多数是稀疏的key(即:key可能比较离散,散列在树的很多地方),而基数树中间节点会按照当前段值存很多指针,导致内存开销较大。即:在性能(树高)和空间占用(内存开销)之间存在不可调和的矛盾。

    二、Adaptive Radix Tree(ARTree)

        为了解决上述问题,提出ARTree。提供多种大小的中间节点和叶子节点,不同节点存key的数目和索引方式不一样。目前主要是:存4个,16个,48个,256个key的节点。总体上来说:提升了cpu cacheline命中率,降低内存开销,另外还可以利用一些指令优化。

        2.1、4 key节点结构体:节点类型 + 大小为4的数组,每个中存1个当前层的key + 大小为4的数组,每个中存当前层key对应的子节点的指针。

        2.2、16 key节点结构体:节点类型 + 大小为16的数组,每个中存1个当前层的key + 大小为16的数组,每个中存当前层key对应的子节点的指针。可以使用二分查找,同时可以使用SIMD技术。

        2.3、48 key节点结构体:节点类型 + 大小256的数组,每个中存1个标识子节点是否存在的值 + 大小48的数组,每个中存当前层key和对应的子节点指针。

        2.4、48 key节点结构体:节点类型 + 大小256的数组,每个中存当前层key和对应的子节点指针。

        2.5、惰性扩展

            类似思路:如果当前节点的子节点数少于2个,则暂时不创建节点,父节点直接指向子节点。

        2.6、路径压缩

            http://131.159.16.103/~leis/papers/ART.pdf

    更多相关内容
  • 同时基数树也是按照字典顺序来组织叶节点的,这种特点使之适合持久化改造,加上他的多道特点,灵活性较强,适合作为区块链的基础数据结构,构建持久性区块时较好的映射各类数据集合。 Nginx基数树的实现  Nginx中...
  • 同时基数树也是按照字典顺序来组织叶节点的,这种特点使之适合持久化改造,加上他的多道特点,灵活性较强,适合作为区块链的基础数据结构,构建持久性区块时较好的映射各类数据集合。 Nginx基数树的实现 Nginx中...

    基数树介绍

           基数树也叫做压缩前缀树,是一种多叉搜索树,对比其他结构跟节省空间。基数树常见于IP路由检索,文本文档的的倒排索引等场景中。同时基数树也是按照字典顺序来组织叶节点的,这种特点使之适合持久化改造,加上他的多道特点,灵活性较强,适合作为区块链的基础数据结构,构建持久性区块时较好的映射各类数据集合。

    Nginx基数树的实现
            Nginx中基数树的实现是一种二叉查找树,具备二叉查找树的所有优点,同时避免了红黑树增删数据是需要通过自身旋转来维持平衡,因此他具有更快的插入、删除速度和更高的内存空间利用率。基数树的key兼顾唯一标识和树平衡维护的功能。的每个节点的key关键字先转换为32为二进制数,然后从左至右开始,0进入左子树,1进入右子树,节点插入的同时自动完成二叉树平衡的维护。
    1.数据结构

    struct ngx_radix_node_s {
        ngx_radix_node_t  *right;/*右孩子节点*/
        ngx_radix_node_t  *left;/*左孩子节点*/
        ngx_radix_node_t  *parent;/*父节点*/
        uintptr_t          value;/*用户自定义结构的数据指针*/
    };

            ngx_radix_tree_t是Nginx基数树的管理和操作类,实现了内存的自己管理。已经分配但是未使用的节点交给free变量,当需要使用节点的时候优先在free变量中重用已有的节点。

    typedef struct {
        ngx_radix_node_t  *root;/*根节点*/
        ngx_pool_t        *pool;/*内存池*/
        ngx_radix_node_t  *free;/*空闲节点*/
        char              *start;/*已分配内存未使用的首地址,也就是下个节点待分配内存的起始地址*/
        size_t             size;/*空闲内存的大小*/
    } ngx_radix_tree_t;

    2.基数树的创建
              基数树的创建和二叉树的创建没有太大的不同,按照基数树的规则一一实现就好。。Nginx基数树中为了减少二叉树的高度(压缩前缀树,压缩就体现在消除不需要的节点带来的分支)使用了掩码。通过掩码来决定树的高度,具体逻辑常见代码注释。

    ngx_radix_tree_t *
    ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
    {
        uint32_t           key, mask, inc;
        ngx_radix_tree_t  *tree;
    
        tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
        if (tree == NULL) {
            return NULL;
        }
    
        tree->pool = pool;
        tree->free = NULL;
        tree->start = NULL;
        tree->size = 0;
    
        tree->root = ngx_radix_alloc(tree);
        if (tree->root == NULL) {
            return NULL;
        }
    
        tree->root->right = NULL;
        tree->root->left = NULL;
        tree->root->parent = NULL;
        tree->root->value = NGX_RADIX_NO_VALUE;
    
        if (preallocate == 0) {
            return tree;
        }
    
        /*
         * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
         * increases TLB hits even if for first lookup iterations.
         * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
         * 8 - 8K, 9 - 16K, etc.  On 64-bit platforms the 6 preallocated bits
         * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
         * to preallocate more than one page, because further preallocation
         * distributes the only bit per page.  Instead, a random insertion
         * may distribute several bits per page.
         *
         * Thus, by default we preallocate maximum
         *     6 bits on amd64 (64-bit platform and 4K pages)
         *     7 bits on i386 (32-bit platform and 4K pages)
         *     7 bits on sparc64 in 64-bit mode (8K pages)
         *     8 bits on sparc64 in 32-bit mode (8K pages)
         */
        /**/
    	/*1.根据系统电脑处理器架构决定基数树的最高层数*/
        if (preallocate == -1) {
            switch (ngx_pagesize / sizeof(ngx_radix_node_t)) {
    
            /* amd64 */
            case 128:
                preallocate = 6;
                break;
    
            /* i386, sparc64 */
            case 256:
                preallocate = 7;
                break;
    
            /* sparc64 in 32-bit mode */
            default:
                preallocate = 8;
            }
        }
    
        mask = 0;
        inc = 0x80000000;
        /*2.掩码初始0层,然后循环处理器架构层次,掩码依次右移逐层增加*/
        while (preallocate--) {
    
            key = 0;
            mask >>= 1;
    		/*2.1异或0x80000000保证掩码最高位是1*/
            mask |= 0x80000000;/*转换二进制1000 0000 0000 0000 0000 0000 0000 0000 */
           /*2.2基数树的首先遍历树的深度,如果为1,向右子树搜索,否则向左子树搜索,如果找到位置有结点,则直接覆盖。否则,则依次创建沿途结点(0或1)并插入在树中。*/
            do {
                if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
                    != NGX_OK)
                {
                    return NULL;
                }
    
                key += inc;
    
            } while (key);
    
            inc >>= 1;
        }
        /*返回构建好的树*/
        return tree;
    }

    3.基数树的查找
          根据基数树的规则,从根节点开始遍历,遇到0遍历左子树,遇到1遍历右子树,最后返回查询结果。

    uintptr_t
    ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
    {
        uint32_t           bit;
        uintptr_t          value;
        ngx_radix_node_t  *node;
    
        bit = 0x80000000;
        value = NGX_RADIX_NO_VALUE;
        node = tree->root;
    
        while (node) {
            if (node->value != NGX_RADIX_NO_VALUE) {
                value = node->value;
            }
    
            if (key & bit) {
                node = node->right;
    
            } else {
                node = node->left;
            }
    
            bit >>= 1;
        }
    
        return value;
    }

            Nginx的基数树要求每个节点key必须可以转换为32位整型,并且因为需要自己管理内存(无形中提高了使用的难度),所以总的来说,即使在Nginx中应用也不广泛。当然这个也没什么奇怪的,基数树解决的主要问题还是字典问题,而字典问题其实关联数组,Hash散列表都可以很好的解决这个问题,这样基数树不常用也就不难理解了。

    展开全文
  • 在有序数据结构的空间中,特别有趣,因为它们的高度和时间复杂度取决于密钥长度(k)而不是中已经存在的密钥数(n)。 在数据集非常庞大的时代,当n的增长速度快于k时,具有与n无关的时间复杂度非常有吸引力。 ...
  • 基数 Go 中基数树的实现。 看唐纳德·R·莫里森。 “PATRICIA——实用的检索算法以字母数字编码的信息”。ACM 杂志,15(4):514-534, 1968 年 10 月或。用法获取包: $ go get github.com/sauerbraten/radix导入...
  • 数据结构基数树(radix_tree)基数树(radix_tree)一,基数树数据的结构的介绍二, 基数树应用场景介绍三,基数树实现总结: 基数树(radix_tree) 基数树数据结构是在字典树(trie_tree)的原理上优化过来的, ...

    基数树(radix_tree)

    基数树数据结构是在字典树(trie_tree)的原理上优化过来的, 是更加合理的使用内存和查询的效率。

    一,基数树数据的结构的介绍

    基数树数据结构是字典树上进行可以前项压缩的数据优化的,基本和字典树数是一样的当是有区别的是进行内存优化的操作。基数树通常使用在ip地址保存操作。

    1, 没有进行前项压缩的结构

    在这里插入图片描述

    2, 前项压缩的操作结构图

    蓝色节点下面都黄色节点没有蓝色的节点就进行压缩的工作

    在这里插入图片描述

    二, 基数树应用场景介绍

    应用用于IP 路由的映射关系中。长整型的哈希冲突问题解决 (nginx,redis,linux中都使用到了)

    三,基数树实现

    1, 在创建基数树预先分配A类地址的数前8位

    预先分配字段是8的由来

    前缀长度前缀首字节
    A类地址8位0xxxxxxx0~127
    B类地址16位10xxxxxx xxxxxxxx128~191
    C类地址24位110xxxxx xxxxxxxx xxxxxxxx192~223
    D类地址不可用1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx224~-239
    E类地址不可用1111xxxx xxxxxxxx xxxxxxxx xxxxxxxx240~255

    对应代码

    	uint32 mask = 0x80000000;
    	
        uint32 preallocate = 8; //预先分配A类地址的数前8bit位
        while (preallocate--)
        {
            mask >>= 1;  // ip 地址掩码 是不同的
            mask |= 0x80000000;
            printf("mask = %u\n", mask);
        }
    

    output

     mask = 2147483648 ==> 1000 0000 0000 0000 0000 0000 0000 0000
     mask = 3221225472 ==> 1100 0000 0000 0000 0000 0000 0000 0000
     mask = 3758096384 ==> 1110 0000 0000 0000 0000 0000 0000 0000
     mask = 4026531840 ==> 1111 0000 0000 0000 0000 0000 0000 0000
     mask = 4160749568 ==> 1111 1000 0000 0000 0000 0000 0000 0000
     mask = 4227858432 ==> 1111 1100 0000 0000 0000 0000 0000 0000
     mask = 4261412864 ==> 1111 1110 0000 0000 0000 0000 0000 0000
     mask = 4278190080 ==> 1111 1111 0000 0000 0000 0000 0000 0000
     mask = 4286578688 ==> 1111 1111 1000 0000 0000 0000 0000 0000
    
    
    #include <stdio.h>
    #include  <stdlib.h>
    #include  <string.h>
    #include <assert.h>
    
    typedef unsigned int	uint32;
    typedef signed int		int32;
    
    /**
     * 默认地址
     */
    #define default_ip "127.0.0.1"
    
    // 基数树 应用场景ip地址映射
    struct cradix_tree_node
    {
        struct cradix_tree * left;
        struct cradix_tree * right;
        char * value; //实际的ip数据
    }cradix_tree;
    
    struct cradix_tree
    {
        struct cradix_tree_node * root;
        uint32  size; //预先分配默认A类地址的数前8位
    };
    
    
    /**
     * 基数树插入ip的地址映射关系
     * @param tree_ptr
     * @param key
     * @param mask
     * @param value
     * @return
     */
    void * cradix_tree_insert(struct cradix_tree * tree_ptr, uint32 key, uint32 mask, void * value)
    {
        assert(tree_ptr != NULL);
        if (!tree_ptr)
        {
            return NULL;
        }
    
        struct cradix_tree_node * cur_node = tree_ptr->root;
        struct cradix_tree_node * next_node = tree_ptr->root;
    
    
        //uint32 mask = 0;
        uint32 bit = 0x80000000;
        while (bit & mask)
        {
            //找到合适的位置插入
            if (bit & key)
            {
                next_node = (struct cradix_tree_node *)cur_node->right;
            }
            else
            {
                next_node = (struct cradix_tree_node *)cur_node->left;
            }
            if (!next_node)
            {
                break;
            }
            cur_node = next_node;
            bit >>= 1; //高位
        }
    
        if (next_node)
        {
            if (cur_node->value)
            {
                cur_node->value = value;
                return next_node;
            }
    
            cur_node->value = value;
            return cur_node;
        }
    
        while (bit & mask)
        {
            next_node = malloc(sizeof(struct cradix_tree_node));
            assert(next_node != NULL);
    
            {
                next_node->left = NULL;
                next_node->right = NULL;
                next_node->value = NULL;
            }
            if (bit & key)
            {
                cur_node->right = (void *)next_node;
            }
            else
            {
                cur_node->left = (void *)next_node;
            }
            bit >>= 1;
            cur_node = next_node;
            next_node = NULL;
        }
    
        if (cur_node)
        {
            cur_node->value = value;
        }
        return cur_node;
    }
    
    /**
     * 创建基数树
     * 预先分配A类地址的数前8bit位
     * @return
     */
    struct cradix_tree * create_radix_tree()
    {
        struct cradix_tree * tree_ptr = malloc(sizeof(struct cradix_tree));
        assert(tree_ptr != NULL);
        if (!tree_ptr)
        {
            return  NULL;
        }
    
        tree_ptr->root = NULL;
        tree_ptr->size = 8;
        tree_ptr->root = malloc(sizeof(struct cradix_tree_node));
        assert(tree_ptr->root != NULL);
        if(!tree_ptr->root)
        {
            return NULL;
        }
        {
            tree_ptr->root->left = NULL;
            tree_ptr->root->right = NULL;
            tree_ptr->root->value = NULL;
        }
    
    
        //建立基数树高度为 32为ip地址的树高度
    
        uint32 inc = 0x80000000; // 对应32位 1000 0000 0000 0000 0000 0000  0000 0000
        uint32 key = 0;
        uint32 mask = 0; //掩码
    
        uint32 preallocate = tree_ptr->size; //预先分配A类地址的数前8bit位
        while (preallocate--)
        {
            key = 0;
            mask >>= 1;  // ip 地址掩码 是不同的
            mask |= 0x80000000;
            // 1000 0000 0000 0000 0000 0000 0000 0000  0000 0000
            /**
               *   ip的掩码 A类地址[8bit]  B类地址[16bit] C类地址[24bit] D,E类型地址不可用
             *   | 类   | 前缀长度   |  前缀
             *   |A类地址|  8位      | 0xxxxxxx                                              |
             *   |B类地址| 16位      | 10xxxxxx   xxxxxxxx                                   |
             *   |C类地址| 24位      | 110xxxxx   xxxxxxxx   xxxxxxxx                        |
             *   |D类地址| 不可用     | 1110xxxx   xxxxxxxx   xxxxxxxx     xxxxxxxx           |
             *   |E类地址| 不可用     | 1111xxxx   xxxxxxxx   xxxxxxxx     xxxxxxxx  			|
             *   
             * mask 对应 就是 A类地址的前8位bit位(默认第32位是1在代码中)
                mask = 2147483648 ==> 1000 0000 0000 0000 0000 0000 0000 0000
                mask = 3221225472 ==> 1100 0000 0000 0000 0000 0000 0000 0000
                mask = 3758096384 ==> 1110 0000 0000 0000 0000 0000 0000 0000
                mask = 4026531840 ==> 1111 0000 0000 0000 0000 0000 0000 0000
                mask = 4160749568 ==> 1111 1000 0000 0000 0000 0000 0000 0000
                mask = 4227858432 ==> 1111 1100 0000 0000 0000 0000 0000 0000
                mask = 4261412864 ==> 1111 1110 0000 0000 0000 0000 0000 0000
                mask = 4278190080 ==> 1111 1111 0000 0000 0000 0000 0000 0000
                mask = 4286578688 ==> 1111 1111 1000 0000 0000 0000 0000 0000
             */
            //遍历从树的顶层向下遍历
            do
            {
                //插入当前节点的数据
                cradix_tree_insert(tree_ptr, key, mask, NULL);
                //这边看出来了吗?  就加到内存溢出 就变成'0'啊
                key += inc; // 举例  == [0x80000000 + 0x80000000] = [0x100000000]  但是无符号int类型放不下这个数据所以 就是 [0x00000000] 高位溢出
            } while (key);
            inc >>= 1;
        }
    
        return tree_ptr;
    }
    
    /**
     * 基数树的查找O(logn)
     * @param tree_ptr
     * @param key
     * @return
     */
    char * cradix_tree_find(struct cradix_tree * tree_ptr, uint32 key)
    {
        assert(tree_ptr != NULL);
        if (!tree_ptr)
        {
            return NULL;
        }
        uint32 bit = 0x80000000;
        struct cradix_tree_node * cur_node = tree_ptr->root;
        void * ptr = NULL;
        while (cur_node)
        {
            if (cur_node->value)
            {
                ptr = cur_node->value;
            }
            if (key & bit)
            {
                cur_node = (struct cradix_tree_node *)cur_node->right;
            }
            else
            {
                cur_node = (struct cradix_tree_node *)cur_node->left;
            }
            bit >>= 1;
        }
        if (!ptr)
        {
            return default_ip;
        }
        return ptr;
    }
    
    /**
     * 递归释放基数树的节点的内存
     * @param tree_ptr
     */
    void cradix_tree_node_destroy(struct cradix_tree_node *tree_ptr)
    {
        if (!tree_ptr)
        {
            return;
        }
        cradix_tree_node_destroy((struct cradix_tree_node *)tree_ptr->left);
        if (tree_ptr->left)
        {
            free(tree_ptr->left);
            tree_ptr->left = NULL;
        }
        cradix_tree_node_destroy((struct cradix_tree_node *)tree_ptr->right);
        if (tree_ptr->right)
        {
            free(tree_ptr->right);
            tree_ptr->right = NULL;
        }
    }
    
    /**
     * 释放基数树内存
     * @param tree_ptr
     */
    void cradix_tree_destroy(struct cradix_tree** tree_ptr)
    {
        assert(tree_ptr != NULL);
        if (!tree_ptr)
        {
            return ;
        }
    
        cradix_tree_node_destroy((struct cradix_tree_node *)(*tree_ptr)->root);
    
        if ((*tree_ptr))
        {
            if ((*tree_ptr)->root)
            {
                free((*tree_ptr)->root);
                (*tree_ptr)->root = NULL;
            }
            free((*tree_ptr));
            (*tree_ptr) = NULL;
    
        }
    }
    
    /**
     * 测试数据结构
     */
    struct ip_proxy {
        uint32  ip; // ip-> uint32
        uint32  mask; // 掩码
        char *  value; //映射的数据
    };
    
    /**2^0 = 1;
     * 2^1 = 2;
     * 2^2 = 4
     * 2^3 = 8
     * 2^4 = 16
     * 2^5 = 32
     * 2^6 = 64
     * 2^7 = 128
     *
     *
     * 测试数据
     *
     */
    struct ip_proxy ip_data[] =
    {         // 128 + 64 + 32 +15 = 96+15 +128 = 111+128 = 239  === 255 - 16 = 239
            { 4009754624/*1110 1111 0000 0000 0000 0000 0000 0000 == 239.0.0.0*/,  4278190080 /*1111 1111 0000 0000 0000 0000 0000 0000 === 255.0.0.0*/, "192.168.1.90"},
            { 4093640704,  4278190080, "192.168.1.91"},
            { 4160749568,  4278190080, "192.168.1.93"},
            { 4244635648, 4278190080, "wangyang"},
            { 3841982464, 4278190080, "shanghui"},
            { 2566914048, 4278190080, "beijing"}
    };
    
    
    
    //void show(struct cradix_tree_node * tree)
    //{
    //    if (!tree)
    //    {
    //        return;
    //    }
    //    printf(" vlaue %s\n", tree->value);
    //    show(tree->left);
    //    show(tree->right);
    //}
    
    
    
    int main(int argc, char *argv[])
    {
    
        struct cradix_tree * tree_ptr = create_radix_tree();
        if (!tree_ptr)
        {
            return -1;
        }
    
        for (int i = 0; i < (sizeof(ip_data) / sizeof(struct ip_proxy)); ++i)
        {
            cradix_tree_insert(tree_ptr, ip_data[i].ip, ip_data[i].mask, ip_data[i].value);
        }
        ///show(tree_ptr->root);
        for (int i = 0; i < (sizeof(ip_data) / sizeof(struct ip_proxy)); ++i)
        {
            printf("ip mask  = %u, ip_proxy = %s, new_ip_proxy = %s\n", ip_data[i].ip, ip_data[i].value, cradix_tree_find(tree_ptr, ip_data[i].ip) );
        }
        //默认代理ip地址
        printf("not ip mask  = %u, ip_proxy = %s, new_ip_proxy = %s\n", 23432, "", cradix_tree_find(tree_ptr, 23432) );
        cradix_tree_destroy(&tree_ptr);
        return EXIT_SUCCESS;
    
    

    总结:

    源码地址:https://github.com/chensongpoixs/cleet_code

    展开全文
  • 基数树(也称为 patricia trie、radix trie或紧凑前缀树)是一种空间优化的树数据结构,它允许仅使用键的前缀插入键(以及与这些键相关联的可选值)以供后续查找而不是整个密钥。 基数树在字符串或文档索引和扫描...
  • Redis5.0 基数树浅析

    2022-01-23 20:50:35
    Rax 是 Redis 内部比较特殊的一个数据结构,它是一个有序字典树(基数树 Radix Tree),按照 key 的字典序排列,支持快速地定位、插入和删除操作。Redis 五大基础数据结构里面,能作为字典使用的有 hash 和 zset。hash...

    前言

    Rax 是 Redis 内部比较特殊的一个数据结构,它是一个有序字典树(基数树 Radix Tree),按照 key 的字典序排列,支持快速地定位、插入和删除操作。Redis 五大基础数据结构里面,能作为字典使用的有 hash 和 zset。hash 不具备排序功能,zset 则是按照 score 进行排序的。rax 跟 zset 的不同在于它是按照 key 进行排序的。
    在这里插入图片描述

    应用

    在这里插入图片描述
    你可以将一本英语字典看成一棵 radix tree,它所有的单词都是按照字典序进行排列,每个词汇都会附带一个解释,这个解释就是 key 对应的 value。有了这棵树,你就可以快速地检索单词,还可以查询以某个前缀开头的单词有哪些。
    也可以将公安局的人员档案信息看成一棵 radix tree,它的 key 是每个人的身份证号,value 是这个人的履历。因为身份证号的编码的前缀是按照地区进行一级一级划分的,这点和单词非常类似。有了这棵树,你就可以快速地定位出人员档案,还可以快速查询出某个小片区都有哪些人。

    数据结构

    rax 中有非常多的节点,根节点、叶节点和中间节点,有些中间节点带有 value,有些中间节点纯粹是结构性需要没有对应的 value。

    struct raxNode {
    	int<1> isKey;// 是否没有key,没有key 的是根节点
    	int<1> isNull; // 是否没有对应的value,无意义的中间节点
    	int<1> isCompressed;// 是否压缩存储
    	int<29> size; // 子节点的数量或者是压缩字符串的长度(isCompressed)
    	byte[] data;// 路由键、子节点指针、value 都在这里
    }
    

    rax 是一棵比较特殊的 radix tree,它在结构上不是标准的 radix tree。如果一个中间节点有多个子节点,那么路由键就只是一个字符。如果只有一个子节点,那么路由键就是一个字符串。后者就是所谓的「压缩」形式,多个字符压在一起的字符串。比如前面的那棵字典树在 Rax 算法中将呈现出如下结构:
    在这里插入图片描述
    图中的深蓝色节点就是「压缩」节点。
    接下来我们再细看 raxNode.data 里面存储的东西,它按照压缩与否分为两种结构。
    压缩结构
    子节点如果只有一个,那就是压缩结构,data 字段如下伪代码所示:

    struct data {
    	optional struct {	// 取决于 header 的 size 字段是否为零
    	byte[] childKey; // 路由键
    	raxNode* childNode;	// 子节点指针
    	} child;
    	optional string value;	// 取决于 header 的 isNull 字段
    }
    

    在这里插入图片描述

    非压缩节点
    如果子节点有多个,那就不是压缩结构,存在多个路由键,一个键是一个字符。

    struct data {
    	byte[] childKeys; // 路由键字符列表
    	raxNode*[] childNodes;// 多个子节点指针
    	optional string value;// 取决于header 的isNull 字段
    }
    

    在这里插入图片描述
    如果子节点只有一个,并且路由键字符串的长度为 1,压缩和非压缩在数据结构表现形式上是一样的,不管 isCompressed 是0 还好是 1,结构都是一样的。

    展开全文
  •  Radix树,即基数树,也称压缩前缀树,是一种提供key-value存储查找的数据结构。与Trie不同的是,它对Trie树进行了空间优化,只有一个子节点的中间节点将被压缩。同样的,Radix树的插入、查询、删除操作的时间...
  • 3.算法设计:带附加头结点单链表将各数据结点按关键字升序连接。 4.编程题:键盘输入n个无符号整数,用链式基数排序实现由小到大排序,输出排序结果。 提示:对于C语言32bit宽的unsigned类型,可以采用16进制形式来...
  • C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
  • 基数树的简单实现

    千次阅读 2019-12-07 02:38:19
    基数树是一种比较节省空间的树结构,下图展示了基数树结构,其中key是树的构建方式,在这里,key是一个32位的整数,为了避免层数过深,所以使用两位代表子节点的索引,基数树就是依据二进制串来生成树结构。...
  • n个关键字序列KlK2Kn称为堆当且仅当该序列满足如下性质(简称为堆性质) (1) Ki K2i 且 Ki K2i+1 小顶堆 或 (2) Ki K2i 且 Ki K2i+1 大顶堆 (1in/2) 若将此序列所存储的向量R[1.n]看做是一棵完全二叉树的存储结构则堆...
  • 《趣学数据结构》课件.rar 《趣学数据结构》课件.rar《趣学...《趣学数据结构》课件.rar《趣学数据结构》课件.rar《趣学数据结构》课件.rar《趣学数据结构》课件.rar《趣学数据结构》课件.rar《趣学数据结构》课件.rar
  • 艺术 高度基于自适应基数树的高压缩基数树() 特征 非常便携-干净的C89实施 设计为主索引数据结构-上面的论文描述了不完全拥有其键的二级索引 非递归更新算法
  • C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
  • 浙大数据结构的ppt
  • 1.1 针对考研数据结构的代码书写规范以及C 与C 语言基础1 1.1.1 考研综合应用题中算法设计部分的代码书写规范1 1.1.2 考研中的C 与C 语言基础3 1.2 算法的时间复杂度与空间复杂度分析基础 12 1.2.1 考研中的算法时间...
  • 数据结构动画演示

    2019-05-06 14:22:22
    该资源包含了几乎所有的数据结构的动画视频,帮助我们更好的理解数据结构与算法的编程思路。 目录如下: 'B的删除.swf', 'B的生长过程.swf', '三元组表的转置.swf', '中序线索化二叉树.swf', '串的顺序存储.swf'...
  • C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
  • \数据结构flash演示\版本1\6-7-8孩子兄弟表示法建立.swf \数据结构flash演示\版本1\6-8-1哈夫曼.swf \数据结构flash演示\版本1\7-2-1十字链表.swf \数据结构flash演示\版本1\7-2-2邻接多重表.swf \数据结构...
  • \数据结构flash演示\版本5 \数据结构flash演示\版本1\1-4 算法和算法分析 冒泡排序.swf \数据结构flash演示\版本1\10-1-1插入排序.swf \数据结构flash演示\版本1\10-2-2直接插入排序.swf \数据结构flash演示\版本1\...
  • 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术...
  • vector A星寻路算法.cpp ...基数排序.cpp 临接矩阵图.cpp 平衡二叉树.cpp 三指针N叉.h 深度寻路算法.cpp 桶排序.cpP 完全二叉树.cpp 完全二叉树.h 希尔排序.cpp 选择排序.cpp 有序二叉树.h 栈.h
  • 数据结构动画演示.7z

    2020-12-09 09:15:30
    资源包含了几乎所有的数据结构的动画视频,帮助我们更好的理解数据结构与算法的编程思路。 目录如下: 'B的删除.swf', 'B的生长过程.swf', '三元组表的转置.swf', '中序线索化二叉树.swf', '串的顺序存储.swf', ...
  • 大学数据结构课程PPT,内容全面,适合掌握C语言的初学者进行学习
  • 桶排序和基数排序212 7.12外部排序216 7.12.1为什么需要一些新的算法217 7.12.2外部排序模型217 7.12.3简单算法217 7.12.4多路合并218 7.12.5多相合并219 7.12.6替换选择219 小结220 练习221 参考文献225 第8章不相...
  • 数据结构;赵宏宇;一、查找 1. 算法设计题 :已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key,编写算法用对分查找求下标i,满足ai-1且aikey。 2. 编程题:输入n个两两互不相等的整数,以...
  • C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...
  • C语言版《数据结构第二版》教程,包含PPT、课程代码、教材习题解答、上机实训以及算法动画演示

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,482
精华内容 12,192
关键字:

数据结构基数树

数据结构 订阅