多叉樹定義為可以有多於兩個子節點的樹。如果多叉樹最多可以有 m 個子節點，則此樹稱為 m 階多叉樹。與其他已研究的樹一樣，m 階多叉樹中的節點將由 m-1 個鍵欄位和指向子節點的指標組成。5 階多叉樹為了簡化 m 階多叉樹的處理，會在每個節點內的鍵上施加某種約束或順序，從而形成 m 階多叉查詢樹……閱讀更多

基本概念多維二叉查詢樹（簡稱 k-d 樹）定義為用於儲存多鍵記錄的資料結構。此結構已被實現以解決統計和資料分析中的一些“幾何”問題。k-d 樹（k 維樹的縮寫）定義為一種用於組織 k 維空間中點的空間劃分資料結構。資料結構 k-d 樹已應用於多種應用，例如涉及多維搜尋鍵的搜尋（例如範圍搜尋和最近鄰搜尋）。k-d 樹被視為二叉空間劃分樹的特例。非正式描述k-d 樹是一種二叉樹……閱讀更多

再平衡演算法可以透過以下方式執行：Day-Stout-Warren 演算法我們可以使用 Day-Stout-Warren 演算法來實現實際的再平衡方法。它是節點數的線性函式。以下是虛擬碼中 Day-Stout-Warren 演算法的基本表示。分配一個名為“偽根”的節點，並將樹的實際根作為偽根的右子節點。呼叫 tree-to-vine 函式，使用偽根作為引數將其轉換為排序連結串列。呼叫 vine-to-tree 函式，使用偽根和樹的大小（元素數量）作為引數將其再次轉換為樹。樹的實際……閱讀更多

我們首先選擇一個記憶體塊。然後我們選擇每個塊內的區域性布隆過濾器。這可能會導致記憶體塊之間不平衡此過濾器效率很高，但假陽性率 (FPR) 很低。首先，分塊布隆過濾器的 FPR（假陽性率）應與相同大小的標準布隆過濾器相同。分塊布隆過濾器由一系列塊 b 組成，這些塊 b 比標準布隆過濾器（布隆過濾器塊）小得多，每個塊都適合一個快取行。分塊布隆過濾器方案與分割槽方案不同，在分割槽方案中，每個位都插入到不同的塊中。分塊布隆過濾器透過以下方式實現：位……閱讀更多

計數器大小我們必須選擇足夠大的計數器以避免溢位。泊松近似建議大小為 4 位/計數器。實現 k = (ln 2)m/n 個計數器的平均負載為 ln 2。計數器負載至少為 16 的機率：≈e-ln2(ln 2)16/16！≈6.78E-17我們考慮 4 位/計數器進行比較。計數器溢位當計數器溢位時，它可能達到其最大值。這種情況以後只會導致假陰性，如果計數器最終下降到 0，而它應該保持為非零值。這種情況的預期時間非常長，但這是我們需要注意的任何不允許假……閱讀更多

基本概念計數布隆過濾器定義為布隆過濾器的廣義資料結構，用於測試在給定一系列元素時給定元素的計數是否小於給定閾值。作為布隆過濾器的廣義形式，存在假陽性匹配的可能性，但沒有假陰性的可能性——換句話說，查詢返回“可能高於或等於閾值”或“肯定低於閾值”。演算法描述計數布隆過濾器中使用的引數大部分與布隆過濾器相同，例如 n，……閱讀更多

布隆過濾器有三個可以權衡的效能指標：計算或執行時間（對應於雜湊函式的數量 k）、過濾器的大小（對應於位數 m）和錯誤機率（對應於假陽性率 f = (1 − p)k）布隆過濾器 (BF) 引入錯誤容限以增強查詢效能和空間效率。布隆過濾器返回真或假。因此，布隆過濾器的結果屬於以下類別之一：真陽性、假陽性、真陰性和假陰性。布隆……閱讀更多

布隆過濾器定義為一種旨在快速有效地識別集合中元素是否存在的資料結構。布隆過濾器實現了一種名為機率資料結構的特定資料結構。此資料結構幫助我們識別元素是否存在於集合中。位向量實現為基本資料結構。這是一個我們用來解釋的小例子123456789101112131415表中的每個空單元格指定一個位，下面的數字是其索引或位置。要將元素新增到布隆過濾器，我們只需雜湊……閱讀更多

多重選擇雜湊之所以得名，是因為它採用了多個雜湊函式的實現。在高層次上，當有多個雜湊函式時，每個專案都對映到多個桶，因此演算法設計者可以自由選擇專案所在的桶。事實證明，這種自由允許演算法獲得比使用單個雜湊函式更均衡的分配。我們將介紹主要的演算法思想和用於證明這些演算法產生的分配範圍的主要數學工具。我們將看到分析……閱讀更多

定義動態完美雜湊被定義為一種解決雜湊表資料結構中衝突的程式設計方法。應用雖然比其雜湊表對應物更佔用記憶體，但此方法非常適合需要對大量元素執行快速查詢、插入和刪除的情況。實現Dietzfelbinger等人解釋了一種動態字典演算法，當將一組m個專案增量新增到字典中時，成員資格查詢始終消耗恆定時間，因此最壞情況時間為O(1)，所需的總儲存空間為O(m)（線性），並且預期攤銷插入和刪除時間為O(1)（攤銷恆定時間）。在動態情況下，當…閱讀更多