概述
本文简要介绍了一些存储引擎存储结构，包括InnoDB, TokuDB, RocksDB, TiDB, CockroachDB, 供大家对比分析
InnoDB
InnoDB 底层存储结构为B+树，结构如下
每个数据节点page结构如下
数据记录record按行存储，record具体格式由row_format决定. 详情可以参考数据内核月报
TokuDB
TokuDB 底层存储结构为Fractal Tree
Fractal Tree的结构与B+树有些类似, 在Fractal Tree中，每一个child指针除了需要指向一个child节点外，还会带有一个Message Buffer ，这个Message Buffer 是一个FIFO的队列，用来缓存更新操作。
例如，一次插入操作只需要落在某节点的Message Buffer就可以马上返回了，并不需要搜索到叶子节点。这些缓存的更新会在查询时或后台异步合并应用到对应的节点中。
RocksDB
RockDB的存储结构如下
RocksDB写入数据时，先写到memtable中,memtable一般为skiplist, memtable写满时转为immutable memtable并刷入Level 0.
Level0中的SST文件中的数据都是有序的，Level0中SST文件之间的数据范围可能存在重叠。 其他Level中的SST文件之间的数据范围不重叠。
RocksDB会以一定的机制从低level compact数据到高level中。
RocksDB中SST文件的结构如下
MyRocks使用的存储引擎就是RocksDB, MyRocks的中RocksDB的数据映射关系参考 之前的月报
TiDB
TiDB的存储结构
- 存储region的位置等元数据信息
- 调度和rebalance regions, TiKV中的Raft leader等信息
- 分配全局事务ID
TiDB的数据映射关系
以下表为例
create table user(user_id int primary key, name varchar(100), email varchar(200)); INSERT INTO user VALUES (1, “bob”, “huang@pingcap.com”); INSERT INTO user VALUES (2, “tom”, “tom@pingcap.com”); 对应到RocksDB中的KV结构如下
CockroachDB
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: \x01k
txn- . - 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的数据映射关系
以下表为例
create table mydb.customers(name varchar(100) primary key, address varchar(100) , URL varchar(100)); insert into mydb.customers values('Apple','1 Infinite Loop, Cupertino, CA','http://apple.com/'); 表结构信息
表中的数据
最后
本文简要介绍了各存储引擎的结构，供大家参考，有错误之处请指正.
参考文档
- https://github.com/facebook/rocksdb
- https://www.percona.com/doc/percona-server/LATEST/tokudb/tokudb_intro.html
- https://github.com/cockroachdb/cockroach/blob/master/docs/design.md
- https://github.com/pingcap/tidb
- https://www.percona.com/live/plam16/sessions/how-we-build-tidb
- https://dev.mysql.com/doc/internals/en/innodb.html
- http://img3.tbcdn.cn/L1/461/1/d0069515c04809a449eda659386afbe966e0d1df
