Linux 内核里的数据结构——基数树

基数树Radixtree

Trie

正如你所知道的，Linux内核提供了许多不同的库和函数，它们实现了不同的数据结构和算法。在这部分，我们将研究其中一种数据结构——基数树Radixtree[1]。在Linux内核中，有两个文件与基数树的实现和API相关：

include/linux/radix-tree.h[2]

lib/radix-tree.c[3]

让我们先说说什么是基数树吧。基数树是一种压缩的字典树