幾乎所有的關(guān)系型數(shù)據(jù)庫和相當(dāng)數(shù)量的非關(guān)系型數(shù)據(jù)庫抽减，在內(nèi)部都實現(xiàn)了B樹作為索引的組織結(jié)構(gòu)睡雇。
之前所說的日志結(jié)構(gòu)的數(shù)據(jù)存儲速种，將數(shù)據(jù)切分成若干規(guī)定大小的數(shù)據(jù)片組織存儲根灯。在各個數(shù)據(jù)片內(nèi)保證數(shù)據(jù)按鍵排序。B樹則將數(shù)據(jù)存放于固定大兄蟹（通常是4KB）的片中姜胖，每次讀寫一個完整片（這是為了配合機械磁盤的設(shè)計）。
可以看出淀散，B樹中只有葉子節(jié)點是包含數(shù)據(jù)本身的(圖中的val)右莱，其他層都是數(shù)據(jù)引用(圖中的ref)。每個節(jié)點的子節(jié)點個數(shù)也叫做B樹的分支度（比如上圖的分支度就是6）档插。
B樹的結(jié)構(gòu)可以保證樹的平衡(balanced)：即對于有n個節(jié)點的B樹慢蜓，樹高為O(log(n))。一個四層高郭膛，分支度為500的B樹晨抡，可以支持存儲最多256TB的數(shù)據(jù)。
在插入操作時则剃，B樹的數(shù)據(jù)片可能會發(fā)生溢出而分裂成兩個半滿的數(shù)據(jù)片耘柱，在這個數(shù)據(jù)轉(zhuǎn)移的過程中，為了防止數(shù)據(jù)庫存儲崩潰棍现，引入了操作日志（WAL调煎，或者叫redo log）。在并發(fā)寫控制上己肮，使用的是latches(一個輕量級的寫鎖)士袄。
還有一些其他的優(yōu)化措施：
- 有些數(shù)據(jù)庫不使用WAL做數(shù)據(jù)容災(zāi)，而是使用copy-on-write模式：將修改過的數(shù)據(jù)另外寫到一個位置朴肺，為這個數(shù)據(jù)節(jié)點的父節(jié)點創(chuàng)建一個新的版本窖剑。因為引入了版本號的概念坚洽，這個措施也被用于并發(fā)控制戈稿。
- 對于單條數(shù)據(jù)比較大的情況，在非葉子節(jié)點中可以不存儲完整鍵讶舰，只存儲可以區(qū)分?jǐn)?shù)據(jù)的唯一鍵即可鞍盗，這樣可以增大B樹的分支度而降低樹高。
- 在各個數(shù)據(jù)節(jié)點之間使用指針串聯(lián)跳昼，方便大范圍順序讀取般甲。
B樹與LSM樹
簡單來說，LSM-trees在寫操作上速度更快鹅颊，而B-trees在讀操作上速度更快敷存。
LSM-trees的優(yōu)點：
B樹至少要把數(shù)據(jù)寫入兩遍：一遍是寫入到數(shù)據(jù)葉子節(jié)點中（如果發(fā)生頁滿分頁的情況，還要再加一遍），一遍是寫入到WAL日志中锚烦。而LSM-trees也會把數(shù)據(jù)寫入多遍（主要發(fā)生在SSTables的合并壓縮過程中）觅闽。這種在數(shù)據(jù)生存期內(nèi)多次寫入數(shù)據(jù)叫做寫入放大(write amplification)。在寫密集操作的場景下涮俄，寫入放大是數(shù)據(jù)庫吞吐的主要瓶頸蛉拙。
相比B樹，LSM樹的寫入放大倍數(shù)較小彻亲，通吃谐可以抵御更高的寫請求，而且LSM樹中主要的寫操作都是追加操作苞尝，相比B樹中的隨機寫入畸肆，效率要高一些。
LSM樹結(jié)構(gòu)導(dǎo)致的磁盤碎片更少野来，它會周期性的合并壓縮SSTables來消除磁盤碎片恼除，而B樹中則可能出現(xiàn)樹不滿的情況，導(dǎo)致磁盤碎片較多曼氛。
LSM-trees的缺點：
定期的SSTables合并壓縮操作會占用部分磁盤資源（IO帶寬）豁辉，影響數(shù)據(jù)庫的吞吐能力。
隨著數(shù)據(jù)增多舀患，更多的IO帶寬需要被進(jìn)行合并壓縮操作的線程占據(jù)徽级，當(dāng)發(fā)生大量寫操作，或者IO帶寬分配不好的情況下聊浅，有可能出現(xiàn)合并壓縮的操作速率遠(yuǎn)低于寫入操作餐抢，各個數(shù)據(jù)片數(shù)據(jù)持續(xù)增大，最終溢出低匙。
B樹的優(yōu)勢在于旷痕，原始數(shù)據(jù)在樹中只有一份，而LSM樹的原始數(shù)據(jù)份數(shù)會隨著更新操作而增加顽冶。
