如何提升 C++ Trie 樹的存取效率？

C++要做一個字典，我用了trie樹，從詞語開始建樹用了差不多3.8s，然後我想「序列化」到磁碟，每次直接讀取，但是最後發現也要3.8s。。。

我這裡的「序列化」不是boost裡面的，是一個深度優先的然後回退就輸出-1做標記。

有沒有其他方法序列化可以更快啊？謝謝～

你可以想辦法把節點分配到連續的內存里（就向資料庫的文件管理部分做的一樣），管理好連續內存里沒用上的部分，然後指針都用index代替，這樣讀寫文件就直接Creating a File Mapping Object 1G都不怕。

說來讀書的時候我也用類似的方法做過無前置知識的分詞系統，靠閱讀大量的文章提取文字之間潛在的關係的一些概率相關的東西，猜哪些字通常都在一起出現。一開始不僅慢，而且沒讀幾篇文章就撐爆內存了。後來用這種方法不僅擴大了數據量（主要是浪費的少），性能還提高了幾十倍。

首先，考慮用一種適合序列化的數據結構來實現 Trie，而不是直接用樹節點。

An Implementation of Double-Array Trie

https://github.com/atframework/atframe_utils/blob/master/include/string/ac_automation.h

Trie建樹的複雜度也是O(n*L)和遍歷一遍字典是一樣的，所以不要指望靠多牛逼的」序列化「方法來提升性能。

如果只是單次查詢，或者查詢成本遠低於建trie成本的話就不用搞什麼trie了，老實線性查找吧。

如果真的查詢量大，還有落地到磁碟的需求，那麼需要設計一下存儲的結構，比如最簡單的把結點換成塊連續存儲，指針換成下標表示，查詢的時候直接用mmap訪問避免數據全部load到內存。

最後，折騰這種東西一定得把磁碟換成SSD的。

可以參考hankcs的基於AC自動機的雙數組trie樹：

hankcs/AhoCorasickDoubleArrayTrie