关于本站
人大经济论坛-经管之家：分享大学、考研、论文、会计、留学、数据、经济学、金融学、管理学、统计学、博弈论、统计年鉴、行业分析包括等相关资源。
经管之家是国内活跃的在线教育咨询平台!
获取电子版《CDA一级教材》
完整电子版已上线CDA网校，累计已有10万+在读~ 教材严格按考试大纲编写，适合CDA考生备考，也适合业务及数据分析岗位的从业者提升自我。
毕业论文
- 开题报告 | 【独家发布】论文 ...
- 开题报告 | 周五双学位论文开 ...
- 开题报告 | 还是找开题报告的 ...
- 开题报告 | 求浙江大学MBA论文 ...
- 开题报告 | 交开题报告
- 开题报告 | 本科毕业论文开题 ...
- 开题报告 | 开题报告、文献检 ...
- 开题报告 | 写开题报告中嘤嘤 ...
TOP热门关键词
坛友互助群 |
扫码加入各岗位、行业、专业交流群 |
Redis实现了不定长压缩前缀的radix tree，用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。
核心数据结构
raxNode是radix tree的核心数据结构，其结构体如下代码所示：
http://image.uczzd.cn/12997014479359791878.jpg?id=0&from=exportiskey：表示这个节点是否包含key
0：没有key
1：表示从头部到其父节点的路径完整的存储了key，查找的时候按子节点iskey=1来判断key是否存在
isnull：是否有存储value值，比如存储元数据就只有key，没有value值。value值也是存储在data中
iscompr：是否有前缀压缩，决定了data存储的数据结构
size：该节点存储的字符个数
data：存储子节点的信息
iscompr=1：压缩模式下，数据格式是：[header strlen=3][xyz][z-ptr](value-ptr?)，只有一个指针，指向下一个节点。size个字符是压缩字符片段
iscompr=0：非压缩模式下，数据格式是：[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)，有size个字符，紧跟着是size个指针，指向每个字符对应的下一个节点。size个字符之间互相没有路径联系。
Rax Insert
以下用几个示例来详解rax tree插入的流程。假设j是遍历已有节点的游标，i是遍历新增节点的游标。
场景一：只插入abcd
http://image.uczzd.cn/13606298901467311417.jpg?id=0&from=exportz-ptr指向的叶子节点iskey=1，使用了压缩前缀。
场景二：在abcd之后插入abcdef
http://image.uczzd.cn/16853522741275545647.jpg?id=0&from=export从abcd父节点的每个压缩前缀字符比较，遍历完所有abcd节点后指向了其空子节点，j = 0， i < len(abcded)。查找到abcd的空子节点，直接将ef赋值到子节点上，成为abcd的子节点。ef节点被标记为iskey=1，用来标识abcd这个key。ef节点下再创建一个空子节点，iskey=1来表示abcdef这个key。
场景三：在abcd之后插入ab
http://image.uczzd.cn/3751861485331295129.jpg?id=0&from=exportab在abcd能找到前两位的前缀，也就是i=len(ab)，j < len(abcd)。将abcd分割成ab和cd两个子节点，cd也是一个压缩前缀节点，cd同时被标记为iskey=1，来表示ab这个key。cd下挂着一个空子节点，来标记abcd这个key。
场景四：在abcd之后插入abABC
abcABC在abcd中只找到了ab这个前缀，即i < len(abcABC)，j < len(abcd)。这个步骤有点复杂，分解一下：
step 1：将abcd从ab之后拆分，拆分成ab、c、d 三个节点。
step 2：c节点是一个非压缩的节点，c挂在ab子节点上。
step 3：d节点只有一个字符，所以也是一个非压缩节点，挂在c子节点上。
step 4：将ABC 拆分成了A和BC， A挂在ab子节点上，和c节点属于同一个节点，这样A就和c同属于父节点ab。
step 5：将BC作为一个压缩前缀的节点，挂在A子节点下。
http://image.uczzd.cn/14104647542024734211.jpg?id=0&from=exportstep 6：d节点和BC节点都挂一个空子节点分别标识abcd和abcABC这两个key。
场景五：在abcd之后插入Aabc
http://image.uczzd.cn/10217066682431926768.jpg?id=0&from=exportabcd和Aabc没有前缀匹配，i = 0，j = 0。将abcd拆分成a、bcd两个节点，a节点是一个非压缩前缀节点。将Aabc拆分成A、abc两个节点，A节点也是一个非压缩前缀节点。将A节点挂在和a相同的父节点上。同上，在bcd和abc这两个节点下挂空子节点来分别表示两个key。
Rax Remove
删除
删除一个key的流程比较简单，找到iskey的节点后，向上遍历父节点删除非iskey的节点。如果是非压缩的父节点并且size > 1，表示还有其他非相关的路径存在，则需要按删除子节点的模式去处理这个父节点，主要是做memove和realloc。
合并
删除一个key之后需要尝试做一些合并，以收敛树的高度。
合并的条件是：
iskey=1的节点不能合并
子节点只有一个字符
父节点只有一个子节点（如果父节点是压缩前缀的节点，那么只有一个子节点，满足条件。如果父节点是非压缩前缀的节点，那么只能有一个字符路径才能满足条件）
结束语[url=Redis radix tree源码解析 http://news.uc.cn/a_2249067945962139756/?from=UCPC]Redis radix tree源码解析 http://news.uc.cn/a_2249067945962139756/?from=UCPC[/url]
免流量费下载资料----在经管之家app可以下载论坛上的所有资源，并且不额外收取下载高峰期的论坛币。
涵盖所有经管领域的优秀内容----覆盖经济、管理、金融投资、计量统计、数据分析、国贸、财会等专业的学习宝库，各类资料应有尽有。
来自五湖四海的经管达人----已经有上千万的经管人来到这里，你可以找到任何学科方向、有共同话题的朋友。
经管之家（原人大经济论坛），跨越高校的围墙，带你走进经管知识的新世界。
扫描下方二维码下载并注册APP
您可能感兴趣的文章
人气文章
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
