2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

Log-Structured Merge Tree 日志結(jié)構(gòu)合并樹

下班閑來無事看了下這種樹的結(jié)構(gòu)，這種樹的結(jié)構(gòu)還是比較簡單的，leveldb的存儲(chǔ)結(jié)構(gòu)用的就是這種。

簡言之就是 將數(shù)據(jù)劃分為多份，每一份存儲(chǔ)一部分?jǐn)?shù)據(jù)。

每一份數(shù)據(jù)都是有序的，這樣來一個(gè)數(shù)據(jù)進(jìn)行查詢的時(shí)候?qū)γ恳徊糠挚梢赃M(jìn)行二分查找，速度可以快很多。

真正存儲(chǔ)的時(shí)候每一部分?jǐn)?shù)據(jù)是不進(jìn)行二分查找的，而是有一個(gè)類似于bitmap的結(jié)構(gòu)記錄著里面有哪些數(shù)據(jù)，這樣查詢的速度又可以增加很多。

由于數(shù)據(jù)量在增加，所以各個(gè)小部分的樹之間有可能存在合并重新排序，所以這種結(jié)構(gòu)被稱為Log-Structured Merge。

轉(zhuǎn)載于:https://my.oschina.net/110NotFound/blog/2872777

總結(jié)

以上是生活随笔為你收集整理的LSM Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。