B+ 樹如何處理重復(fù)鍵？ B+ 樹有兩種主要方法處理重復(fù)鍵，以確保索引的效率和正確性：

追加記錄ID (Append Record Id)

• 這種方法通過(guò)在每個(gè)鍵后面追加對(duì)應(yīng)的元組的 唯一記錄ID （通常是頁(yè)面ID和偏移量），使每個(gè)鍵在索引中變得獨(dú)一無(wú)二。
• 優(yōu)勢(shì) ：在B+樹中，即使鍵被追加了記錄ID，數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）仍然可以進(jìn)行 部分鍵查找 ，僅使用原始屬性值進(jìn)行搜索，然后沿著葉子節(jié)點(diǎn)掃描以找到所有匹配項(xiàng)。
• 缺點(diǎn) ：這種方法會(huì) 增加索引的大小 ，因?yàn)槊總€(gè)鍵都包含了額外的記錄ID信息。

使用溢出葉子節(jié)點(diǎn) (Overflow Leaf Nodes)

• 這種方法允許葉子節(jié)點(diǎn)“溢出”到額外的 溢出頁(yè)面 或 溢出節(jié)點(diǎn) 中，這些溢出頁(yè)面專門存儲(chǔ)重復(fù)的鍵。這些溢出頁(yè)面會(huì)垂直地鏈接到主葉子節(jié)點(diǎn)。
• 優(yōu)勢(shì) ：這種方法 不會(huì)存儲(chǔ)任何冗余信息 來(lái)使鍵唯一。
• 缺點(diǎn) ：它增加了索引的 復(fù)雜性 ，因?yàn)樵趻呙枞~子節(jié)點(diǎn)時(shí)需要額外邏輯來(lái)跟隨溢出頁(yè)面，尤其是在反向掃描時(shí)。

聚簇索引 (Table Clustering)

• 表聚簇是指DBMS使用索引來(lái) 強(qiáng)制表本身元組的物理排序順序 。
• 在PostgreSQL等系統(tǒng)中，這是一個(gè) 一次性操作 。這意味著表在首次聚簇后會(huì)根據(jù)索引排序，但隨著后續(xù)的修改（插入、更新、刪除），元組的物理順序可能會(huì)再次變得無(wú)序。
• 然而，在MySQL、SQL Server和Oracle等其他系統(tǒng)中，你可以聲明一個(gè)表是聚簇表，這樣 無(wú)論插入順序如何，底層物理存儲(chǔ)都將保持排序 。
• 優(yōu)勢(shì) ：對(duì)于某些查詢，這允許DBMS直接在表數(shù)據(jù)上執(zhí)行 二分查找 ，而無(wú)需通過(guò)索引本身，從而提高性能。在MySQL中，主鍵索引的葉子節(jié)點(diǎn)實(shí)際上就是元組本身，使得沿著葉子節(jié)點(diǎn)掃描就等同于對(duì)表的順序掃描。

字典樹 / Radix (Tries / Radix Trees)

• 字典樹 (Trie) 是一種樹形數(shù)據(jù)結(jié)構(gòu)，它不存儲(chǔ)鍵的完整副本，而是存儲(chǔ)鍵的 數(shù)字或原子子集 （如單個(gè)字節(jié)或位）。鍵的值通過(guò)從根到葉子的路徑隱式表示，并且不需要像B+樹那樣進(jìn)行重新平衡操作。
• 基數(shù)樹 (Radix Tree) 是字典樹的一種 特化形式 ，它省略了所有只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)（即進(jìn)行了 垂直壓縮 ）?；鶖?shù)樹有時(shí)也被稱為 Patricia樹 。
• 特性

它們的形狀僅取決于 鍵空間的分布和長(zhǎng)度 ，而不取決于現(xiàn)有鍵或插入順序，因此是確定性的。

所有操作的復(fù)雜性是 O(k) ，其中k是鍵的長(zhǎng)度。這意味著，如果在查找過(guò)程中發(fā)現(xiàn)前綴不匹配，可以立即停止，而無(wú)需遍歷到底層。

基數(shù)樹在 點(diǎn)查詢 方面通常比B+樹更快，但在 順序掃描 方面可能較慢。

鍵的字節(jié)序和編碼技巧

• 并非所有屬性類型都能直接分解為基數(shù)樹所需的 二進(jìn)制可比數(shù)字 。
• 例如，無(wú)符號(hào)整數(shù)可能需要翻轉(zhuǎn)字節(jié)序（對(duì)于小端系統(tǒng)），帶符號(hào)整數(shù)需要調(diào)整二進(jìn)制補(bǔ)碼，浮點(diǎn)數(shù)需要先分類再作為無(wú)符號(hào)整數(shù)處理。復(fù)合鍵需要對(duì)每個(gè)屬性分別進(jìn)行轉(zhuǎn)換。這些都需要特殊的編碼技巧來(lái)確保按字節(jié)比較的正確性。

倒排索引解決 B+ 樹解決不了的問(wèn)題（文本查詢）

• 傳統(tǒng)的B+樹和哈希索引擅長(zhǎng)處理“點(diǎn)查詢”（精確匹配）和“范圍查詢”，例如查找郵政編碼或日期范圍內(nèi)的記錄。
• 然而，它們 不適用于關(guān)鍵詞搜索 ，例如在大量文本中查找包含特定詞語(yǔ)的文檔，或執(zhí)行LIKE '%word%'這樣的模式匹配。這是因?yàn)锽+樹需要對(duì)整個(gè)鍵進(jìn)行精確或范圍查找，而不能查找鍵內(nèi)部分子元素。
• 倒排索引 (Inverted Index) 專門用于解決這個(gè)問(wèn)題。它存儲(chǔ)了 單詞到包含這些單詞的記錄的映射 。
• 需要考慮的因素

存儲(chǔ)內(nèi)容 (What to Store) ：最簡(jiǎn)單的形式是存儲(chǔ)單詞本身并映射到記錄ID。但也可以包含 詞頻、位置信息以及其他元數(shù)據(jù) ，以便支持更復(fù)雜的查詢。

更新時(shí)機(jī) (When to Update) ：頻繁更新倒排索引成本很高。因此，許多DBMS會(huì)維護(hù)輔助數(shù)據(jù)結(jié)構(gòu)來(lái) 分批暫存更新 ，然后定期批量更新索引。

• 支持的查詢類型 ：倒排索引能夠支持 短語(yǔ)搜索 （查找包含特定順序詞語(yǔ)的記錄）、 鄰近搜索 （查找兩個(gè)詞語(yǔ)在指定距離內(nèi)出現(xiàn)的記錄）以及 通配符搜索 （匹配復(fù)雜模式）。
• 許多主流DBMS都原生支持倒排索引，也有專門的全文搜索數(shù)據(jù)庫(kù)系統(tǒng)（如Elasticsearch）。

高級(jí)索引技術(shù)：部分索引 (Partial Indexes)

• 部分索引 是指僅在表的 子集 上創(chuàng)建索引。通過(guò)在 CREATE INDEX 命令中添加 WHERE 子句來(lái)實(shí)現(xiàn)，指定哪些元組應(yīng)該包含在索引中。
• 優(yōu)勢(shì) ：這種方法可以 減小索引的大小 ，降低維護(hù)成本，并減少不必要數(shù)據(jù)對(duì)緩沖池（Buffer Pool）的污染。
• 常見用例 ：按日期范圍分區(qū)索引，例如為每個(gè)月或每年創(chuàng)建單獨(dú)的索引。

避免回表 (Avoiding Table Lookups / Index-Only Scans)

• “避免回表”是指查詢所需的所有數(shù)據(jù)都可以在索引中直接找到，而無(wú)需再去訪問(wèn)實(shí)際的表（堆）中的元組。這可以顯著減少磁盤I/O和提高查詢性能。
• 覆蓋索引 (Covering Indexes) ：如果處理查詢所需的所有字段都可以在索引中找到，那么DBMS就不需要檢索原始元組。這是DBMS 自動(dòng)判斷 和利用的特性。
• 索引包含列 (Index Include Columns) ：這是一種允許在索引中嵌入 額外列 的技術(shù)，這些額外列雖然不作為搜索鍵的一部分，但會(huì)存儲(chǔ)在索引的葉子節(jié)點(diǎn)中。這使得即使查詢需要這些非搜索鍵的列，也能實(shí)現(xiàn)索引唯一掃描。PostgreSQL 11和SQL Server支持此功能。

函數(shù)表達(dá)式索引 (Functional/Expression Indexes)

• 函數(shù)表達(dá)式索引 允許你將 函數(shù)或表達(dá)式的輸出 作為鍵來(lái)構(gòu)建索引，而不是直接使用原始列的值。
• 示例 ：如果經(jīng)常需要查詢某個(gè)日期時(shí)間字段是星期幾，可以創(chuàng)建一個(gè)索引在 EXTRACT(dow FROM login_timestamp) 的結(jié)果上，這樣查詢時(shí)DBMS就可以直接利用這個(gè)索引。
• 關(guān)鍵 ：DBMS的查詢優(yōu)化器必須能夠識(shí)別哪些查詢可以使用這種基于表達(dá)式的索引。
• 要注意的是，用于創(chuàng)建表達(dá)式索引的函數(shù)必須是 不可變 的（即給定相同的輸入，每次調(diào)用都會(huì)產(chǎn)生相同的輸出，不會(huì)因外部狀態(tài)而改變）。