Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to parse the Redis radix tree source code, the content of the article is of high quality, so the editor will share it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Redis implements radix tree with variable length compression prefix, which is used to store all the key information corresponding to slot in cluster mode. This article details how to implement radix tree in Redis.

Core data structure

RaxNode is the core data structure of radix tree, and its structure is as follows:

Typedef struct raxNode {uint32_t iskey:1; uint32_t isnull:1; uint32_t iscompr:1; uint32_t size:29; unsigned char data [];} raxNode

Iskey: indicates whether this node contains key

0: no key

1: indicates that the key is completely stored in the path from the header to its parent node. When searching, the child node iskey=1 is used to determine whether the key exists.

Isnull: whether there is a value stored, for example, there is only key for storing metadata, there is no value. Value values are also stored in data

Iscompr: prefix compression determines the data structure of data storage

Size: the number of characters stored by this node

Data: stores information about child nodes

Iscompr=1: in compressed mode, the data format is: [header strlen=3] [xyz] [z-ptr] (value-ptr?), with only one pointer to the next node. Size characters are compressed character fragments

Iscompr=0: in uncompressed mode, the data format is: [header strlen=0] [abc] [a-ptr] [b-ptr] [c-ptr] (value-ptr?), with size characters, followed by size pointers to the next node corresponding to each character. There is no path connection between size characters.

Rax Insert

Here are a few examples to detail the process of rax tree insertion. Suppose j is a cursor that traverses an existing node and I is a cursor that traverses a new node.

Scenario 1: insert only abcd

Z-ptr points to the leaf node iskey=1, using the compression prefix.

Scenario 2: insert abcdef after abcd

Compared with each compressed prefix character of the abcd parent node, after traversing all abcd nodes, it points to its empty child node, j = 0, I

< len(abcded)。 查找到abcd的空子节点，直接将ef赋值到子节点上，成为abcd的子节点。ef节点被标记为iskey=1，用来标识abcd这个key。ef节点下再创建一个空子节点，iskey=1来表示abcdef这个key。

Scenario 3: insert ab after abcd

Ab can find the first two prefixes in abcd, that is, i=len (ab), j

< len(abcd)。 将abcd分割成ab和cd两个子节点，cd也是一个压缩前缀节点，cd同时被标记为iskey=1，来表示ab这个key。 cd下挂着一个空子节点，来标记abcd这个key。

Scenario 4: insert abABC after abcd

AbcABC only found the prefix ab in abcd, that is, 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子节点下。 step 6：d节点和BC节点都挂一个空子节点分别标识abcd和abcABC这两个key。 场景五：在abcd之后插入Aabc abcd和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, indicating that other unrelated paths exist, then the parent node needs to be processed according to the mode of deleting child nodes, mainly for memove and realloc.

Merge

After deleting a key, you need to try to do some merging to converge the height of the tree.

The conditions for the merger are:

Nodes of iskey=1 cannot be merged

The child node has only one character

The parent node has only one child node (if the parent node is a compressed prefix node, then there is only one child node, which meets the condition. If the parent node is a node with an uncompressed prefix, then only one character path can satisfy the condition)

On how to parse the Redis radix tree source code to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.