基数树是一种有序的字典树，按照key的字典顺序进行排序，可以支持对key的快速定位、插入和删除操作。Redis自己实现一个基数树的主要目的是在性能与内存使用之间找到适当的平衡，同时可以满足许多不同需求的功能齐全的基数树的实现方式。
基数树可以被认为是前缀树的一种优化形式，首先我们来看一下基础的前缀树数据结构，对于前缀树，其具有三个特点：
前缀树的根节点不包含任何字符，除了根节点之外每个节点只有一个字符。
从根节点到某一个节点
x
路径上所有节点字符组成的字符串，便是x
节点对应的字符串。对于一个节点，它的每一个子节点，其对应的字符都不相同。
基数树在组织形式上与前缀树有一定的差异，其节点不但可以表示单一字符，同时也可以表示字符串的公共子串。无论是单一字符，还是公共子串，其主旨的思想都是利用字符串的公共前缀来减少查询时间。而对于基数树来说，每一个叶子节点都是一个数据条目。
尽管用户对于基数树的实用性以及适用性越来越感兴趣，但是Redis的作者发现，实现一个健壮的基数树，尤其是具有较为灵活的迭代器、同时功能齐全的基数树是一件十分困难的事情。因为在处理节点的拆分与合并以及各种边缘情况时，非常容易出错。
基数树节点
基数树节点分类
对于基数树的节点来说，存在普通节点与压缩节点两种区分。对于一个普通节点，如果其布局格式如下所示：
+----+---+--------+--------+--------+--------+|HDR |xyz| x-ptr | y-ptr | z-ptr |dataptr |+----+---+--------+--------+--------+--------+
上述这个普通节点表示这个基数树节点具有三个子节点，分别通过匹配字符x
，y
以及z
来转移到对应的子节点，而这个节点与其子节点的关联是通过存储在xyz
后面的三个子节点指针实现的。
而压缩节点，其在内存之中的分布格式则如下所示：
+----+---+---------+|HDR |ABC|child-ptr|+----+---+---------+
如何理解这种压缩节点呢，可以考虑如下的场景，在基数树的某一个局部位置，从某一个节点开始到另外一个节点结束中间的每个节点均只有一个子节点，也就意味着在这个基数树的局部，树形结构已经退化成一个链表结构。如果依然按照普通基数树节点一样为这个链表中的每一个节点都创建一个真实的基数树节点的话，一来会浪费内存；二来在节点到其子节点的匹配跳转过程中，可能会因为缓存失效而导致系统的性能降低。既然在基数树局部这个链表结构里，节点转移的路由是唯一的，那么可以将链表之中的节点整合成为一个压缩节点，这样既可以节约内存的使用，同时还可以提高遍历访问的效率。
基数树节点数据结构
Redis为基数树节点定义的数据数据为：
typedef struct raxNode {uint32_t iskey:1;uint32_t isnull:1;uint32_t iscompr:1;uint32_t size:29;unsigned char data[];} raxNode;
这里需要为raxNode
节点中的指针数据约定一下各自的名称，文章的后续将都会以此名称进行称呼：
数据指针，即基数树键空间之中，指向某一个Key对应的Value数据的指针。当
raxNode.iskey
为1的情况下，在raxNode
节点数据的最后字段dataptr
便会存储一个数据指针，用于指向当前节点所代表的Key对应的数据Value。子节点指针，则是指代在当前基数树节点
raxNode
之中存储的，用于指向其子节点的指针。
这个数据结构中：
raxNode.iskey
，这个字段表示当前节点是否是一个完整的key。如果节点是一个key，那么从基数树的根节点下降到当前节点路径上的字符所组成的字符串便是该基数树key-value空间中的一个key。需要注意的是，这个key是不包含当前节点的内容的，另外raxNode
只有是key的时候，才会保存对应的value，并拥有数据指针dataptr
。raxNode.isnull
，只有raxNode.iskey
为1的时候，才会有数据指针，但是也会存在只有Key而没有Value的情况。raxNode.isnull
标记这个节点是否为一个空节点，如果raxNode.isnull
被设置为1，则该节点不需要为数据指针分配存储内存。raxNode.iscompr
，该字段用于标记当前节点是普通节点还是压缩节点。raxNode.size
，对于压缩节点，这个字段表示压缩数据的长度；如果这个节点是非压缩节点，则表示该节点的子节点的个数。raxNode.data
，这个字段用来存储这个基数树节点的数据载荷，前面介绍的关于基数树节点的内存分布，raxNode
结构体的前四个字段都是属于HDR的内容，而子节点的分支字符，子节点的指针以及数据指针都是存储在raxNode.data
这个字段之中的。
基数树节点的基础操作逻辑
针对这个基数树的节点数据结构，Redis在src/rax.c源文件之中提供了几个宏定义用于实现关于raxNode
的基础操作。
#define raxPadding(nodesize)
通过前面对于raxNode
节点描述，我们可以知道，raxNode
前面的HDR
数据固定占用4个字节的空间，存储在raxNode.data
中的各个指针数据固定占用4个字节或者8个字节的空间，而节点中存储字符的个数是变长的，处于对齐的考虑，需要在raxNode.data
中补充几个字节用于数据对齐，raxPadding
便是用于计算需要几个空字节来进行对齐。
接下来我们便可以通过下面这个宏，来获取一个给定的raxNode
实际占用的内存大小。
#define raxNodeCurrentLength(n)
最后我们可以通过下面这两个宏，来获取指向存储在raxNode.data
数据中第一个以及最后一个子节点指针的指针，注意这两个宏所返回的数据类型为raxNode**
，因为raxNode.data
中存储的是raxNode*
，也就是指向raxNode
的指针，而下面这两个宏返回的是指向raxNode.data
中数据的指针，也就是指向 raxNode
指针的指针，故此应该是raxNode**
类型。
#define raxNodeLastChildPtr(n)#define raxNodeFirstChildPtr(n)
除了上述的四个宏定义之外，Redis还定义了一个用于分配初始化raxNode
节点的函数：
raxNode *raxNewNode(size_t children, int datafield);
在这个创建函数中，参数children
表示这个待创建的raxNode
节点具有的子节点个数，datafield
则表示这个节点是否拥有一个存储数据指针的空间，这个函数调用会根据参数计算节点所需要的内存，并分配空间，并对其中的数据字段进行初始化，最终返回这个新的raxNode
节点的指针。
如果一个已经存在的基数树节点，其raxNode.data
数据之中不包含数据指针，当我们希望为其分配一个数据指针时，可以调用下面这个函数来进行操作：
raxNode *raxReallocForData(raxNode *n, void *data);
不过需要注意的是，raxReallocForData
这个函数仅仅为数据指针分配了新的空间，并没有执行数据的赋值。如果需要将数据指针写入raxNode.data
数据之中的话，则需要通过下面这个函数来执行：
void raxSetData(raxNode *n, void *data);
此外，我们可以通过下面这个函数来获取raxNode
节点之中的数据指针：
void *raxGetData(raxNode *n);
当给定节点raxNode.isnull
字段为空的时候，那么表示当前节点不存在数据指针，raxGetData
会返回一个空值。
基数树节点中子节点的插入与删除
raxNode *raxAddChild(raxNode *n, unsigned char c, raxNode **childptr, raxNode ***parentlink);
raxAddChild
这个函数会向给定的基数树节点n
中按照字典顺序插入一个表示字符c
的子节点，由于在向节点中插入新的子节点的操作可能会导致基数树节点的内存被重新分配，因此这个函数会返回新的n
节点的指针。新创建的子节点的指针会通过childptr
参数返回，这个节点在raxNode.data
中存储的指针的位置会通过parentlink
的参数进行返回。这里需要注意的是，待插入节点n
不可以是压缩节点，必须是一个普通的节点。
例如，下图所显示的，一个给定的基数树普通节点，该节点具有四条分支子节点，分别用于匹配abde
四个字符，
当需要向这个节点之中插入一个表示匹配字符c
的子节点：
raxNode *raxCompressNode(raxNode *n, unsigned char *s, size_t len, raxNode **child)
而上面这个raxCompressNode
则用于将一个普通基数树节点n
转化为一个压缩节点，这个待转化的节点n
不能拥有任何子节点指针，函数会返回节点n
的新指针。
与插入节点相反的，Redis从一个给定的基数树节点之中删除子节点，是通过下面这个raxRemoveChild
函数来实现的。
raxNode *raxRemoveChild(raxNode *parent, raxNode *child)
raxRemoveChild
这个函数会从父节点parent
中删除child
子节点，并返回parent
的新指针。与raxAddChild
类似，也需要在删除完子节点指针之后，对parent
节点的内存进行调整，并重新分配内存。
