The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases( IEEE International Conference on Data Engineering)
摘要
RAM容量的發(fā)展使大多數(shù)數(shù)據(jù)庫都能放到內(nèi)存中。索引是內(nèi)存數(shù)據(jù)庫的至關(guān)重要的瓶頸。
傳統(tǒng)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)如二叉平衡搜索樹在現(xiàn)代硬件上效率低，因為不能充分利用CPU cache。哈希表效率很高，但是只支持點查詢。
ART 查找性能極好，也支持高效的插入與刪除，節(jié)省空間，解決了最壞情況下的空間消耗。
簡介
對于OLTP，生成的執(zhí)行計劃就是索引操作序列，因此索引效率是影響性能的至關(guān)重要的因素。
傳統(tǒng)的內(nèi)存索引結(jié)構(gòu)是二叉搜索樹，如T樹，處理器架構(gòu)的巨大改變使得其效率較低。原因是——原因是CPU cache的增大和不同的主存速度(NUMA)使統(tǒng)一內(nèi)存訪問(UMA)時間的基本假設(shè)過時。
（因此有了CCS樹和CSB+樹，基于緩存敏感對二叉搜索樹和B+樹的改進）
緩存敏感B+樹(CSB+ Tree)有更緩存友好的內(nèi)存訪問機制，更新貴。而且二叉樹和B+樹在現(xiàn)代CPU上都還有一個問題就是：比較的結(jié)果不能簡單的預(yù)測出來，the long pipelines of modern CPUs stall, which causes additional latencies after every second comparison (on average).
三類索引（搜索樹、哈希表、前綴樹）
搜索樹：k路查詢樹和FAST(Fast Architecture Sensitive Tree)用SIMD同時進行多個比較。FAST通過最優(yōu)化利用cache line和TLB來減少cache miss。它在查找上效率不錯，但是不支持持續(xù)性的update。對于OLTP來說，持續(xù)的更新插入刪除都是不可避免的，另一種解決方法delta又會導致額外的開銷。
哈希表快，兩個缺點：只支持點查詢；不能很好處理數(shù)據(jù)的增長，溢出時需要O(n)重構(gòu) 哈希表
前綴樹Trie tree：時間復雜度O(k)，k是字符串長度。在大量數(shù)據(jù)下，因為它的時間復雜度只和k有關(guān)，和n無關(guān)，很好的性質(zhì)。
多數(shù)前綴樹都要通過設(shè)置全局的合法扇出系數(shù)(valid fanout parameter)來平衡樹的高度與空間效率。ART的節(jié)點用了高效和緊湊的數(shù)據(jù)結(jié)構(gòu)，可以基于孩子節(jié)點的個數(shù)動態(tài)選擇。而路徑壓縮和lazy expansion允許ART折疊節(jié)點最終降低樹的高度來更有效的索引長key。
相關(guān)工作：
CSB+，B+樹更深的優(yōu)化G. Graefe and P.-A. Larson, “B-tree indexes and CPU caches,” in ICDE,2001.
k-ary search
FAST
Tire
Kiss-Tree
Adaptive Radix Tree
準備工作
radix tree與基于比較的樹的區(qū)分點：
- radix tree的高度取決于key的長度，一般與樹中元素的個數(shù)無關(guān)
- radix不需要平衡
- key按詞典順序存放
- 路徑代表葉子節(jié)點的key，key的存放是隱性的，可以由路徑重構(gòu)
兩種節(jié)點，內(nèi)部節(jié)點 映射(部分key—其他節(jié)點)，葉子節(jié)點 存相應(yīng)key的value。中間節(jié)點一般是2的s次冪個指針的數(shù)組。樹遍歷的時候，s bit個chunk的key用于索引數(shù)組，無需比較得到下一個孩子節(jié)點。s叫span，對于radix tree的性能至關(guān)重要，s和key的length共同決定了樹的高度。
在完全搜索樹中，每次比較會排除一半的值，而在平衡radix tree當s>1時能排除更多。當n>2^(k/s)時，radix tree的高度就比搜索樹低了。
假設(shè)對于large key的比較時間復雜度是O(k)，那么對于搜索樹時間復雜度是O(k*log n)，而radix tree時間復雜度是O(k)。
span較大的radix tree比傳統(tǒng)搜索樹效率高。
Adaptive Nodes
span大，當大多孩子指針都是空的時候就造成了空間浪費
隨著span的增加，樹的高度線性下降，空間消耗指數(shù)級增加。
ART用的是相對大的span有不同扇出的不同節(jié)點大小
這種節(jié)點不會影響樹的結(jié)構(gòu)，只會影響節(jié)點的大小。通過減少節(jié)點空間消耗，自適應(yīng)節(jié)點允許用更大的span來增加性能。
持續(xù)的更新導致在每次更新后會重新構(gòu)建節(jié)點大小，很貴； 這里用集中節(jié)點類型，每個都有不同的扇出。根據(jù)非空孩子的個數(shù)用對應(yīng)的節(jié)點。當一個節(jié)點由于插入用完了，就用更大的節(jié)點類型取代。由于刪除不滿了，就換更小類型的節(jié)點。
中間節(jié)點的數(shù)據(jù)結(jié)構(gòu)
節(jié)點大小是不同的
span為8，可以存的部分key就是1byte，實現(xiàn)起來簡單，也不用進行位操作和標記操作
沒有用鍵值對的list，而是將list分成了鍵 和 指針兩部分——可以存的更緊湊
Node4：存4個孩子指針。key有序(1byte4 + 8byte4)
Node16：存5-16還孩子指針。key可以通過二分查找或者在SIMD中并行比較來快速查找。(1byte16 + 8byte16)
前面的key數(shù)組里面存的是key的值，在查找的時候是通過查找key數(shù)組來看它有沒有，然后根據(jù)它所在key數(shù)組的位置(偏移量去)去指針數(shù)組中找
Node48：查找已經(jīng)比較貴了。key不再直接存放了，用256元素的數(shù)組它可以直接用鍵字節(jié)索引。如果一個節(jié)點有17到48個子指針，這個數(shù)組將索引存儲到第二個數(shù)組中，該數(shù)組最多包含48個指針。這比256個8byte指針節(jié)省空間，因為索引只需要6bit。(256 * 6bit + 48 * 8byte)
這里直接有長度256的key數(shù)組，它的位置就代表key的值，里面存的是它在指針數(shù)組的偏移量，因為指針數(shù)組長度48，可以用6bit表示，節(jié)省空間
Node256：只有一個數(shù)組，里面直接存的是孩子指針。(256*8byte)
每個節(jié)點還有一個固定大小的頭文件,存節(jié)點類型、孩子的個數(shù)還有壓縮路徑
葉子節(jié)點的數(shù)據(jù)結(jié)構(gòu)
假設(shè)是唯一key(非唯一 key可以加一個tuple id)
值的存儲方式
- 單值葉子：用額外的葉子節(jié)點類型存一個值
- 多值葉子：用前面的中間節(jié)點存，只不過把里面的指針存成值
- 指針/值結(jié)合：如果值能放到指針里，不需要單獨的節(jié)點類型；內(nèi)部節(jié)點存指針的地方既可以存指針也可以存值?？梢杂妙~外的1bit來區(qū)分指針和值。
單值葉子最常用，因為它允許key和變長的值存在一個節(jié)點中。但是它增加了樹的高度，查找時需要額外的指針遍歷；多值葉子需要key有相同的長度；指針/值結(jié)合高效，并且可以存變長的key。
內(nèi)部節(jié)點的壓縮
lazy expansion：內(nèi)部節(jié)點只有需要分成兩個以上葉子節(jié)點時才會創(chuàng)建。像圖中FOO，只有另一個以F為前綴的節(jié)點插入進來才會創(chuàng)建F節(jié)點。這個優(yōu)化需要key存在葉子中或者能從數(shù)據(jù)庫中檢索。
路徑壓縮：在只有一個孩子時移除所有的內(nèi)部節(jié)點，圖中的A會被移除。兩種方法
- 悲觀：在每個內(nèi)部節(jié)點中都有一個變長的Partial key vector。包含的是所有被移除的單路的節(jié)點。通過查找這個vector來進行比較在處理到下一個孩子節(jié)點前。
- 樂觀：只存前面的單路節(jié)點的個數(shù)。查找時關(guān)鍵字跳過這幾個字符繼續(xù)進行比較。在最后到葉子節(jié)點時需要再次比較來防止錯誤。
樂觀和悲觀方法都可以保證內(nèi)部節(jié)點只有一個孩子。樂觀方法對于長字符串更有利但是需要額外的一次檢查。悲觀方法需要更多的空間，而且不同的節(jié)點大小會增加內(nèi)存的碎片化。這里用的兩種混合方式，會存一個定長的如8byte，當存的單路節(jié)點超過了，用樂觀方法。
路徑壓縮和lazy expansion，前者針對中間節(jié)點只有一個內(nèi)部節(jié)點孩子的情況，后者針對只有一個葉子節(jié)點孩子的情況。
算法
查找：需要注意lazy expansion和path compression
插入：簡單情況下插入到一個葉子節(jié)點，如果它滿了需要把它升級。如果是lazy expansion的情況，發(fā)現(xiàn)了一個葉子節(jié)點，這個時候需要把它變成一個中間節(jié)點和葉子節(jié)點。
批量加載：在一個已經(jīng)存在的關(guān)系上加速構(gòu)建索引：使用每個鍵的第一個字節(jié)，將鍵/值對以基數(shù)劃分為256個分區(qū)，并創(chuàng)建適當類型的內(nèi)部節(jié)點。在返回內(nèi)部節(jié)點之前，通過使用每個鍵的下一個字節(jié)遞歸地對每個分區(qū)應(yīng)用大容量加載過程來創(chuàng)建其子節(jié)點。
刪除：刪除與插入是對稱的 如果當前節(jié)點只有一個孩子，用它的孩子節(jié)點取代，根據(jù)path compression進行調(diào)整。
空間消耗
稠密的數(shù)據(jù)無需優(yōu)化也有很好的空間利用率，但是稀疏的數(shù)據(jù)會導致一些節(jié)點包含了大多空指針，其他節(jié)點很稠密。
adaptive nodes解決了這個問題，保證key的任何分布通過局部優(yōu)化都能緊密存儲。
最壞的情況，每個key都用多個adaptive nodes， lazy expansion和path compression。
構(gòu)建二進制可比關(guān)鍵字
radix中的key是詞典按位排序的。這對于ASCII編碼的字符串是很好用的，但是對于不符合大多數(shù)數(shù)據(jù)類型，如負的有符號整型就比一個正整型大。
需要一種轉(zhuǎn)換key的規(guī)則。在進行排序和查找前都需要把key先轉(zhuǎn)換為二進制可比的key。
轉(zhuǎn)換函數(shù)t，比較函數(shù)memcmp
無符號整型：本身已經(jīng)是二進制可比deletion。只是需要注意機器是先高位后低位還是先低位后高位
有符號整型：有符號補碼整型——因為負數(shù)需要補碼只比價二進制數(shù)的話是比正數(shù)大的。可以把首位XOR1
下面的不再介紹了。
評估
先用不同的數(shù)據(jù)類型測試
然后都整合到Hyper中，用TCP-C測試
查找——數(shù)據(jù)量由少到多，總體介紹性能，然后用performance counter來看周期、指令、Misp.Branches、L3 Hit、L3 Miss更好的理解結(jié)果
單線程、多線程(不同步)
Pipeline對多線程的影響很大
Cache的影響——樹的結(jié)構(gòu)從Cache受益，因為樹上層的節(jié)點被頻繁訪問，一般都會緩存在cache中。
隨機查找對與cache是最不利的情況，隨著偏斜的增大，ART與哈希表的性能會更好，因為他們比較少，而FAST需要更多的比較，cache受限小了又要受CPU多次比較的影響。
另外除了上面的所有的cache給了一個索引用，更現(xiàn)實的情況是cache中有多個索引和其他數(shù)據(jù)。模擬這種情況，用round-robin的方式在多個數(shù)據(jù)結(jié)構(gòu)上查找數(shù)據(jù)。哈希表受cache影響較小(它無論如何都不能有效利用cache)，樹形索引會隨cache增大性能提升。
更新——盡管ART隨著樹的增大需要動態(tài)的替換中間節(jié)點，仍要比其他數(shù)據(jù)類型要快。adaptive node需要20%的代價比起只用node256，但是它節(jié)省的空間是值得的。
批量插入，此外有序的key能大量提升插入速度。
端到端測試
把這些索引都在hyper數(shù)據(jù)庫中用TCP-C進行了測試
結(jié)論
快速且節(jié)省空間的內(nèi)存數(shù)據(jù)庫索引
high fanout、lazy expansion、path compression來降低樹的高度
通過動態(tài)選擇內(nèi)部節(jié)點來解決radix tree的通病最壞情況下的空間消耗
未來的工作：索引上的并發(fā)控制與同步
latch-free同步
節(jié)點大小相同的節(jié)省空間的radix tree（不再是動態(tài)變化扇出，而是動態(tài)變化用來記錄key的bits）
ART的實現(xiàn) Github
C版本
Java版本 實現(xiàn)的比較完整，包括文中提到的將可以轉(zhuǎn)化為二進制可比
