??當RocksDB收到一條Get()請求時奋刽，會依次從memtable瓦侮、immutable memtable和SST files中去查找。SST files是按照層次組織的佣谐。
??在level 0肚吏，文件是按照flush的時間戳順序存儲。每個file的key range（FileMetaData.smallest and FileMetaData.largest）大部分情況下都是有重疊的狭魂，所以需要查詢每一個L0 file罚攀。
??compaction會定期執(zhí)行，從Ln層選擇SST files雌澄，然后merge到一起生成一個新的SST file斋泄，然后下推到Ln+1層。所以镐牺，key/value s從L0依次沿著LSM tree 下降到Ln層炫掐。執(zhí)行compaction操作時會把key/value s進行排序，然后拆分到多個文件中睬涧。從level 1到level n,SST files按照key 排序募胃，且每個文件的key range互相不重疊。為了check一個key可能存在于哪一個一個SST file中畦浓，RocksDB并沒有依次遍歷每一個SST file然后去檢查key是否在這個file的key range 內痹束，而是執(zhí)行二分搜索算法（FileMetaData.largest ）去定位這個SST file。二者相比讶请，復雜度從O(N)下降到了O(logn)祷嘶。然而，針對某些極端情況夺溢，logn的復雜度仍然無法接受论巍。比如：上層到下一層的文件的扇出率是10的話，則level 3就有1000個文件风响。要將一個key locate到一個特定的文件环壤，需要執(zhí)行10次比較操作。這對于每秒執(zhí)行幾百萬次查詢的in-memory database來說钞诡，是個很大的消耗郑现。
??針對這個問題，解決方法可以如下：LSM tree build成功后荧降，每一個層次的SST file的位置是對齊的接箫，甚至，相對于下一層次的文件的位置也是對齊的朵诫⌒劣眩基于次，我們可以縮小二分搜索的范圍。
file 1 file 2
+----------+ +----------+
level 1: | 100, 200 | | 300, 400 |
+----------+ +----------+
file 1 file 2 file 3 file 4 file 5 file 6 file 7 file 8
+--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+
level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | | 410, 450 |
+--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+
??如上圖废累，Level 1有2個文件邓梅，level 2有8個文件。現在邑滨，我們要檢索 key=80日缨。基于FileMetaData.largest 的二分搜索可以得出file 1是候選文件掖看。然后比較80與file 1的FileMetaData.smallest和FileMetaData.largest來判斷80是否在file1的range中匣距。比較結果是80 小于FileMetaData.smallest (100)，所以file 1不可能包含key 80哎壳。接下來去檢索level 2,毅待。通常情況下，我們會對level 2中的8個文件去執(zhí)行二分查找归榕。但是尸红，由于我們已經知道了80 小于100且只有file 1到file3才有可能包含小于100的key，我們就可以很明確地排除其他文件而不去檢索刹泄。此時外里，我們的檢索范圍就從8個文件縮減到了3個。
??再看一個例子循签，現在要檢索的是key=230。在level1上執(zhí)行二分搜索可以將key先定位到 file2疙咸。然后將230與file 2的上下界進行比較县匠，得出key 是小于file 2's FileMetaData.smallest 300。即使撒轮，此時我們沒有在level 1中找到目標key乞旦，但是可以推斷出目標key是在200和300之間。此時题山，level 2中key range不包含[200, 300]的SST file可以被排除兰粉。此時，我們只需要檢索level 2中的file5 和file 6即可顶瞳。
??基于上面的方法玖姑，我們可以在compaction時提前在level 1構建一些指針，這些指針指向level 2的某個范圍內的文件列表慨菱。比如焰络，level 1中的file1 左指針指向level 2中的file 3，右指針指向level 2中的file4符喝。File 2的左右指針分別指向level2 中的file 6和7闪彼。查找時，這些指針可以用來確定二分查找的文件范圍协饲。
??benchmark中顯示SST file Index優(yōu)化提升了5%的look up qps畏腕。
