在計算機科學中，基數樹，或稱壓縮前綴樹，是一種更節省空間的Trie（前綴樹）。對於基數樹的每個節點，如果該節點是確定的子樹的話，就和父節點合併。基數樹可用來構建關聯數組。 用於IP 路由。 信息檢索中用於文本文檔的倒排索引。
基本介紹
- 中文名：基數樹
- 外文名：Radix Tree
- 學科：計算機科學
- 定義：一種節省空間的前綴樹
- 套用：用來構建關聯數組
- 有關術語：前綴樹
簡介,前綴樹,套用,
簡介
基數樹可看做是以二進制位串為關鍵字的trie 樹，是一種多叉樹形結構，同時又類似多層索引表，每箇中間節點包含指向多個子節點的指針數組，葉子節點包含指向實際的對象的指針(由於對象不具備樹節點結構，因此將其父節點看做葉節點)。基數樹也被設計成多道樹，以提高磁碟互動性能。同時，基數樹也是按照字典序來組織葉節點的，這種特點使之適合持久化改造，加上它的多道特點，靈活性較強，適合作為區塊鏈的基礎數據結構，構建持久性區塊時較好地映射各類數據集合上。基數樹支持插入、刪除、查找操作。查找包括完全匹配、前綴匹配、前驅查找、後繼查找。所有這些操作都是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），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜尋下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。
有兩種不同的反向索引形式：
- 一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
- 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
後者的形式提供了更多的兼容性（比如短語搜尋），但是需要更多的時間和空間來創建。
