一、背景
基数树在前面已经讲过了，将一个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、路径压缩