本文簡要介紹了一些存儲引擎存儲結構，包括InnoDB, TokuDB, RocksDB, TiDB, CockroachDB, 供大家對比分析
InnoDB 底層存儲結構為B+樹，結構如下
B樹的每個節點對應innodb的一個page，page大小是固定的，一般設為16k。
其中非葉子節點隻有鍵值，葉子節點包含完成資料。
InnoDB按segment, extent, page方式管理page
每個資料節點page結構如下
資料記錄record按行存儲，record具體格式由row_format決定.
TokuDB 底層存儲結構為Fractal Tree
Fractal Tree的結構與B+樹有些類似, 在Fractal Tree中，每一個child指針除了需要指向一個child節點外，還會帶有一個Message Buffer ，這個Message Buffer 是一個FIFO的隊列，用來緩存更新操作。
例如，一次插入操作隻需要落在某節點的Message Buffer就可以馬上傳回了，并不需要搜尋到葉子節點。這些緩存的更新會在查詢時或背景異步合并應用到對應的節點中。
RockDB的存儲結構如下
RocksDB寫入資料時，先寫到memtable中,memtable一般為skiplist, memtable寫滿時轉為immutable memtable并刷入Level 0.
Level0中的SST檔案中的資料都是有序的，Level0中SST檔案之間的資料範圍可能存在重疊。
其他Level中的SST檔案之間的資料範圍不重疊。
RocksDB中SST檔案的結構如下
TiDB的存儲結構
TiDB是分布式存儲，分為兩個部分TiKV和Placement Driver server。
TiKV用于存儲真正的資料，TiKV由分布在不同機器上的RocksDB執行個體組成。
資料按範圍劃分為一個個Region. 并且會盡量保持每個 Region 中儲存的資料不超過一定的大小(這個大小可以配置，目前預設是 64MB). 同一Region分布在不同的RocksDB執行個體中，一個RocksDB執行個體包含多個Region.
圖中，Region4有三個副本分布在三個RocksDB執行個體中，這三個Region副本組成一個RaftGroup，副本間通過Raft協定保證一緻性。
Placement Driver server（PD）， 也是一個叢集，也通過Raft協定保證一緻性。PD主要有以下作用：
存儲region的位置等中繼資料資訊
排程和rebalance regions, TiKV中的Raft leader等資訊
配置設定全局事務ID
TiDB的資料映射關系
以下表為例
對應到RocksDB中的KV結構如下
|Key |Values|
| ------------- |:-------------:|
|user/1|bob [email protected]|
|user/2|tom [email protected] |
CockroachDB的存儲結構
CockroachDB的也是分布式存儲，其結構和TiDB類似。CockroachDB按範圍劃分為Range，Range預設為64M，Range的存儲為RocksDB， CockroachDB的一個node包含多個RocksDB執行個體。
Range副本分布在不同的node中，通過Raft協定保證一緻。
Range的中繼資料資訊也儲存在Range中(靠前的Range中).
System keys come in several subtypes:
Global keys store cluster-wide data such as the "meta1" and "meta2" keys as well as various other system-wide keys such as the node and store ID allocators.
Store local keys are used for unreplicated store metadata (e.g. the StoreIdent structure). "Unreplicated" indicates that these values are not replicated across multiple stores because the data they hold is tied to the lifetime of the store they are present on.
Range local keys store range metadata that is associated with a global key. Range local keys have a special prefix followed by a global key and a special suffix. For example, transaction records are range local keys which look like: x01ktxn-.
Replicated Range ID local keys store range metadata that is present on all of the replicas for a range. These keys are updated via Raft operations. Examples include the range lease state and abort cache entries.
Unreplicated Range ID local keys store range metadata that is local to a replica. The primary examples of such keys are the Raft state and Raft log.
CockroachDB的資料映射關系
表結構資訊
|/system/databases/mydb/id | 51|
|/system/tables/customer/id | 42|
|/system/desc/51/42/address |69|
|/system/desc/51/42/url |66
表中的資料
|/51/42/Apple/69| 1 Infinite Loop, Cupertino, CA|
本文簡要介紹了各存儲引擎的結構，供大家參考，有錯誤之處請指正.
<a href="https://github.com/facebook/rocksdb">https://github.com/facebook/rocksdb</a>
<a href="https://www.percona.com/doc/percona-server/LATEST/tokudb/tokudb_intro.html">https://www.percona.com/doc/percona-server/LATEST/tokudb/tokudb_intro.html</a>
<a href="https://github.com/cockroachdb/cockroach/blob/master/docs/design.md">https://github.com/cockroachdb/cockroach/blob/master/docs/design.md</a>
<a href="https://github.com/pingcap/tidb">https://github.com/pingcap/tidb</a>
<a href="https://www.percona.com/live/plam16/sessions/how-we-build-tidb">https://www.percona.com/live/plam16/sessions/how-we-build-tidb</a>
<a href="https://dev.mysql.com/doc/internals/en/innodb.html">https://dev.mysql.com/doc/internals/en/innodb.html</a>
<a href="http://img3.tbcdn.cn/L1/461/1/d0069515c04809a449eda659386afbe966e0d1df">http://img3.tbcdn.cn/L1/461/1/d0069515c04809a449eda659386afbe966e0d1df</a>