基数树(Radix Tree)

简介

Radix tree(也被称为 radix trie，或者 compact prefix tree)是一种空间优化的前缀树(prefix tree)数据结构。

针对这对这样的稀疏长整型数据查找，能高速且节省空间地完成映射

应用场景

• IP 路由；
• 倒排索引；
• IDR（ID Radix）机制；
• Linux 基数树（radix tree），内存管理；
• Redis Radix tree；

参考

1. 数据结构之 Radix Tree
2. 详解 Linux 内核 Radix 树算法的实现 - 黎棉麒的独立博客
3. 图解 Redis 中的 Radix 树 - 云+社区 - 腾讯云