基數樹

基數樹可看做是以二進制位串為關鍵字的trie 樹，是一種多叉樹形結構，同時又類似多層索引表，每個中間節點包含指向多個子節點的指針數組，葉子節點包含指向實際的對象的指針(由於對象不具備樹節點結構，因此將其父節點看做葉節點) ^[1]  。基數樹也被設計成多道樹，以提高磁盤交互性能。同時，基數樹也是按照字典序來組織葉節點的，這種特點使之適合持久化改造，加上它的多道特點，靈活性較強，適合作為區塊鏈的基礎數據結構，構建持久性區塊時較好地映射各類數據集合上。基數樹支持插入、刪除、查找操作。查找包括完全匹配、前綴匹配、前驅查找、後繼查找。所有這些操作都是O(k)複雜度，其中k是所有字符串中最大的長度。

在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。

Trie這個術語來自於retrieval。根據詞源學，trie的發明者Edward Fredkin把它讀作/ˈtriː/ "tree"。但是，其他作者把它讀作/ˈtraɪ/ "try"。trie中的鍵通常是字符串，但也可以是其它的結構。trie的算法可以很容易地修改為處理其它結構的有序序列，比如一串數字或者形狀的排列。比如，bitwise trie中的鍵是一串位元，可以用於表示整數或者內存地址。trie樹常用於搜索提示。如當輸入一個網址，可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果，可以返回前綴最相似的可能。

在計算機科學中，關聯數組（Associative Array），又稱映射（Map）、字典（Dictionary）是一個抽象的數據結構，它包含着類似於（鍵，值）的有序對。一個關聯數組中的有序對可以重複（如C++中的multimap）也可以不重複（如C++中的map）。這種數據結構包含以下幾種常見的操作：

字典問題是設計一種能夠具備關聯數組特性的數據結構。解決字典問題的常用方法，是利用散列表，但有些情況下，也可以直接使用二叉查找樹或其他結構。

許多程序設計語言內置基本的數據類型，提供對關聯數組的支持。而內容定址存儲器則是硬件層面上實現對關聯數組的支持。

倒排索引（Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。

有兩種不同的反向索引形式：

後者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建。