unordered_map 性能被吊打！我用基數樹讓內存池性能暴漲幾十倍的秘密
作者：xiaokang1998
基數樹真的是一個被低估的數據結構。在合適的場景下，它能帶來數倍甚至數十倍的性能提升。
今天要和大家聊一個特別有意思的話題——基數樹。
說實話，我第一次聽到這個名詞的時候，內心是懵逼的。基數？樹？這玩意兒到底是啥？
直到有一天，我在研究TCMalloc內存池源碼的時候，發現了一個神奇的現象：為什么Google的工程師不用std::unordered_map來做頁號映射，而要自己實現一個看起來很復雜的數據結構？
帶著這個疑問，我深入研究了一下，結果發現了一個寶藏——基數樹！
一個讓我震驚的性能對比
先來看個數據，直接震撼你的小心臟：
測試場景：100萬次查找操作
std::unordered_map： 40878微秒
基數樹： 714微秒
性能提升： 57.2521倍！這還只是中等規模的測試，在大規模場景下，差距會更加夸張。
基數樹到底是個啥玩意兒？
好，現在我用最通俗的話給大家解釋一下基數樹。
簡單粗暴地說，基數樹就是一個超級大數組！
沒錯，就這么簡單。
比如你要存儲鍵值對，傳統的做法是：
- std::map：用紅黑樹，需要比較、旋轉，O(log n)時間
- std::unordered_map：用哈希表，需要計算哈希、處理沖突，平均O(1)但有常數開銷
而基數樹呢？直接把鍵當作數組的下標！
// 傳統方式
unordered_map[123] = ptr; // 需要計算hash(123)，可能還要處理沖突
// 基數樹方式
array[123] = ptr; // 直接訪問！O(1)且常數極小是不是超級簡單？
動手實現一個基數樹（一級）
talk is cheap，show me the code！
const uint32_t MAX_KEY = (1 << 20) - 1;
// ============ 基數樹實現 ============
template<int BITS = 20> // 20位，支持100萬條目 800 0000
class SimpleRadixTree {
private:
staticconstsize_t SIZE = 1 << BITS;
void** array_;
public:
SimpleRadixTree() {
array_ = newvoid*[SIZE];
memset(array_, 0, SIZE * sizeof(void*));
cout << "創建了支持 " << SIZE << " 條目的基數樹" << endl;
cout << "理論內存: " << (SIZE * 8) / (1024) << " KB" << endl;
}
~SimpleRadixTree() {
delete[] array_;
}
// 設置鍵值對 - O(1)時間！
void set(uint32_t key, void* value) {
if (key >= SIZE) {
cerr << "錯誤: 鍵 " << key << " 超出范圍 [0, " << (SIZE-1) << "]" << endl;
return;
}
array_[key] = value;
}
// 獲取值 - O(1)時間！
void* get(uint32_t key) {
if (key >= SIZE) returnnullptr;
return array_[key];
}
// 刪除鍵
void remove(uint32_t key) {
if (key < SIZE) {
array_[key] = nullptr;
}
}
// 統計已使用的條目數
size_t count_used() const {
size_t count = 0;
for (size_t i = 0; i < SIZE; ++i) {
if (array_[i] != nullptr) {
count++;
}
}
return count;
}
// 獲取支持的最大鍵值
uint32_t max_key() const {
return SIZE - 1;
}
};就這么幾行代碼，我們就實現了一個高性能的一級基數樹！
基數樹的核心：用空間換時間。
性能大PK：基數樹 VS unordered_map
我專門寫了個測試程序，在我的Ubuntu機器上跑了一下：
void performance_battle() {
cout << "\n========== 性能大PK開始 ==========" << endl;
constint TEST_COUNT = 1000000;
// 準備測試數據
vector<uint32_t> keys;
cout << "準備 " << TEST_COUNT << " 個測試鍵..." << endl;
for(int i = 0; i < TEST_COUNT; i++) {
keys.push_back(i);
}
cout << "數據準備完成，開始測試..." << endl;
// ========== 測試 unordered_map ==========
cout << "\n測試 unordered_map..." << endl;
unordered_map<uint32_t, void*> hashmap;
auto start = chrono::high_resolution_clock::now();
// 插入測試
for(int i = 0; i < TEST_COUNT; i++) {
hashmap[keys[i]] = reinterpret_cast<void*>(i + 1);
}
// 查找測試
for(int i = 0; i < TEST_COUNT; i++) {
volatilevoid* result = hashmap[keys[i]];
(void)result; // 防止編譯器優化掉
}
auto end = chrono::high_resolution_clock::now();
auto hashmap_time = chrono::duration_cast<chrono::microseconds>(end - start);
// ========== 測試基數樹 ==========
cout << "測試基數樹..." << endl;
SimpleRadixTree<20> radix_tree;
start = chrono::high_resolution_clock::now();
// 插入測試
for(int i = 0; i < TEST_COUNT; i++) {
radix_tree.set(keys[i], reinterpret_cast<void*>(i + 1));
}
// 查找測試
for(int i = 0; i < TEST_COUNT; i++) {
volatilevoid* result = radix_tree.get(keys[i]);
(void)result; // 防止編譯器優化掉
}
end = chrono::high_resolution_clock::now();
auto radix_time = chrono::duration_cast<chrono::microseconds>(end - start);
// ========== 輸出結果 ==========
cout << "\n=== 性能大PK結果 ===" << endl;
cout << "測試規模: " << TEST_COUNT << " 次操作" << endl;
cout << "unordered_map: " << hashmap_time.count() << " 微秒" << endl;
cout << "基數樹: " << radix_time.count() << " 微秒" << endl;
if (radix_time.count() > 0) {
double speedup = (double)hashmap_time.count() / radix_time.count();
cout << "性能提升: " << speedup << " 倍" << endl;
if (speedup > 5) {
cout << "基數樹性能碾壓！" << endl;
} elseif (speedup > 2) {
cout << " 基數樹明顯更快！" << endl;
} else {
cout << "性能相當" << endl;
}
}
// 驗證結果正確性
cout << "\n驗證結果正確性..." << endl;
bool correct = true;
for(int i = 0; i < 1000; i++) { // 驗證前1000個結果
void* hash_result = hashmap[keys[i]];
void* radix_result = radix_tree.get(keys[i]);
if (hash_result != radix_result) {
cout << "結果不一致！鍵: " << keys[i] << endl;
correct = false;
break;
}
}
if (correct) {
cout << "結果驗證通過，兩種方法結果一致！" << endl;
}
}在我的機器上跑出來的結果：
=== 性能大PK結果 ===
測試規模: 1000000 次操作
unordered_map: 40878 微秒
基數樹: 714 微秒
性能提升: 57.2521 倍50+倍的性能提升！ 這還只是中等規模的測試。
為什么會有這么大的差距？
- 基數樹：直接數組訪問，沒有任何額外計算
- unordered_map：需要計算哈希值、處理沖突、內存分散訪問
基數樹在內存池中的神奇應用
現在來看看基數樹的實際應用場景——內存池！
在內存池系統中，我們需要根據內存地址快速找到對應的內存塊信息（Span）。
傳統方式可能是這樣：
// 傳統內存池的頁號映射
unordered_map<PageID, Span*> page_to_span;
// 哈希查找，較慢
Span* find_span(void* ptr) {
PageID page_id = (uintptr_t)ptr >> 12; // 假設4KB頁面
std::lock_guard<std::mutex> lock(map_mutex_);// 還要加鎖
auto it = page_to_span.find(id);
return (it != page_to_span.end()) ? it->second : nullptr;
}用基數樹優化后：
// 基數樹版本的頁號映射
SimpleRadixTree<28> page_map; // 支持1TB地址空間
// 不需要加鎖
Span* find_span(void* ptr) {
PageID page_id = (uintptr_t)ptr >> 12;
return (Span*)page_map.get(page_id); // 直接數組訪問，超快！
}這就是為什么TCMalloc、jemalloc這些高性能內存池都在用基數樹的原因！
一個完整的內存池應用示例
// ============ 內存池應用演示 ============
struct Span {
uint32_t page_id;
uint32_t num_pages;
bool in_use;
void* free_list;
Span(uint32_t pid, uint32_t pages, bool used = true)
: page_id(pid), num_pages(pages), in_use(used), free_list(nullptr) {}
};
class MemoryPool {
private:
SimpleRadixTree<24> page_map_; // 24位，支持16M頁，相當于64GB地址空間
vector<Span*> spans_; // 保存所有Span，用于清理
public:
~MemoryPool() {
for(auto* span : spans_) {
delete span;
}
}
// 注冊內存塊
void register_span(Span* span) {
spans_.push_back(span);
// 為這個Span的每一頁都建立映射
for(uint32_t i = 0; i < span->num_pages; i++) {
uint32_t page_id = span->page_id + i;
page_map_.set(page_id, span);
}
cout << "注冊Span: 起始頁號=" << span->page_id
<< ", 頁數=" << span->num_pages << endl;
}
// 根據地址快速找到所屬的內存塊
Span* addr_to_span(void* ptr) {
// 假設頁面大小為4KB，即PAGE_SHIFT=12
uint32_t page_id = (reinterpret_cast<uintptr_t>(ptr) >> 12) & 0xFFFFFF; // 取低24位
returnreinterpret_cast<Span*>(page_map_.get(page_id));
}
// 根據頁號查找Span
Span* page_to_span(uint32_t page_id) {
returnreinterpret_cast<Span*>(page_map_.get(page_id));
}
// 釋放內存時，快速定位到對應的Span
bool free_memory(void* ptr) {
Span* span = addr_to_span(ptr); // O(1)時間找到Span！
if(span && span->in_use) {
cout << "找到地址 " << ptr << " 對應的Span: 頁號" << span->page_id << endl;
returntrue;
}
returnfalse;
}
};看到沒？有了基數樹，內存池的地址查找變成了O(1)操作，這對高并發場景下的內存分配性能提升是巨大的！
當然，這里只是簡單展示一下基數樹的應用思路。實際的內存池項目要復雜得多，想學習完整實現的同學不妨看看：三周肝出4000行代碼，我的內存池竟然讓malloc"破防"了！性能暴漲7.37倍背后的技術真相
什么時候該用基數樹？
基數樹雖然牛逼，但也不是萬能的。什么時候用呢？
適合用基數樹的場景：
- 鍵的范圍相對固定且已知
- 鍵分布比較密集
- 對查找性能要求極高
- 內存充足的環境
不適合用基數樹的場景：
- 鍵的范圍非常大且分布稀疏
- 內存嚴重受限的環境
- 鍵是字符串等復雜類型
進階：多層基數樹
當鍵的范圍太大時（比如64位地址空間），1層基數樹就不夠用了。這時候我們可以用多層基數樹。
簡單來說，就是把一個超級大數組拆分成多個小數組的組合：
// 2層基數樹示意
template<int BITS = 36> // 支持Linux 64位地址空間
class PageMap2 {
private:
// 位數分配：盡量均勻分配
staticconstint LEAF_BITS = BITS / 2; // 18位
staticconstint ROOT_BITS = BITS - LEAF_BITS; // 18位
staticconstsize_t ROOT_SIZE = 1ULL << ROOT_BITS;
staticconstsize_t LEAF_SIZE = 1ULL << LEAF_BITS;
struct Leaf {
void* values[LEAF_SIZE];
Leaf() {
memset(values, 0, sizeof(values));
}
};
Leaf* root_[ROOT_SIZE];
public:
PageMap2() {
memset(root_, 0, sizeof(root_));
cout << "二級基數樹初始化完成！" << endl;
cout << "支持地址空間: " << (1ULL << BITS) << " 頁 ("
<< ((1ULL << BITS) * 4096) / (1024ULL*1024*1024*1024) << " TB)" << endl;
cout << "固定內存開銷: " << sizeof(root_) / (1024*1024) << " MB" << endl;
}
~PageMap2() {
// 清理所有分配的葉子節點
for(size_t i = 0; i < ROOT_SIZE; i++) {
delete root_[i];
}
}
// 獲取值 - 兩次數組訪問，仍然是O(1)！
void* get(uint64_t key) {
if(key >= (1ULL << BITS)) returnnullptr;
uint64_t i1 = key >> LEAF_BITS; // 高位作為一級索引
uint64_t i2 = key & (LEAF_SIZE - 1); // 低位作為二級索引
if(root_[i1] == nullptr) returnnullptr;
return root_[i1]->values[i2];
}
// 設置值 - 按需分配葉子節點
void set(uint64_t key, void* value) {
if(key >= (1ULL << BITS)) return;
uint64_t i1 = key >> LEAF_BITS;
uint64_t i2 = key & (LEAF_SIZE - 1);
// 按需分配葉子節點
if(root_[i1] == nullptr) {
root_[i1] = new Leaf();
cout << "分配新的葉子節點: " << i1 << endl;
}
root_[i1]->values[i2] = value;
}
};這樣可以支持36位鍵空間（256TB地址），但內存是按需分配的，不會浪費。
在我最近帶領學員做的高性能內存池項目中，我們就采用了這種二級基數樹的設計思路，不過做了更多的工程優化。實際效果非常不錯，相比原來的unordered_map方案，性能提升了10倍以上。
感興趣的朋友可以看這篇文章：三周肝出4000行代碼，我的內存池竟然讓malloc"破防"了！性能暴漲7.37倍背后的技術真相
我的使用心得
用了基數樹這么久，我總結幾個心得：
- 不要被"樹"這個名字迷惑了，基數樹本質上就是數組
- 在高性能場景下，基數樹是神器，特別是內存池、路由表這些場景
- 多層基數樹是進階版本，1層夠用就別搞復雜
編譯運行試試看
想要自己試試的同學，把文章中的代碼整合一下，用這個命令編譯：
g++ -std=c++11 -O2 radix_tree_test.cpp -o test
./test在我的Ubuntu 20.04上跑得飛快！
寫在最后
基數樹真的是一個被低估的數據結構。
在合適的場景下，它能帶來數倍甚至數十倍的性能提升。Google、Facebook這些大廠的底層庫都在大量使用基數樹，絕對不是沒有道理的。
下次如果你遇到需要快速鍵值查找的場景，特別是鍵范圍相對固定的情況，不妨試試基數樹。說不定會有意想不到的驚喜！
責任編輯：趙寧寧
來源：
跟著小康學編程
