tidb-in-action

3.1 表数据与 Key-Value 的映射关系

本小节为大家介绍 TiDB 中数据到 (Key, Value) 键值对的映射方案。这里的数据主要包括两个方面:

  1. 表中每一行的数据,以下简称表数据
  2. 表中所有索引的数据,以下简称索引数据

下面分别对这两个方面进行介绍。

3.1.1 表数据与 Key-Value 的映射关系

在关系型数据库中,一个表可能有很多列。要将一行中各列数据映射成一个 (Key, Value) 键值对 ,需要考虑如何构造 Key。首先,OLTP 场景下有大量针对单行或者多行的增、删、改、查等操作,要求数据库具备快速读取一行数据的能力。因此,对应的 Key 最好有一个唯一 ID (显示或隐式的 ID),以方便快速定位。其次,很多 OLAP 型查询需要进行全表扫描。如果能够将一个表中所有行的 Key 编码到一个区间内,就可以通过范围查询高效完成全表扫描的任务。 基于上述考虑:

  1. 为了保证同一个表的数据放在一起,方便查找,TiDB 会为每个表分配一个表 ID,用 TableID 表示。表 ID 是一个整数,在整个集群内唯一。
  2. TiDB 会为表中每行数据分配一个行 ID,用 RowID 表示。行 ID 也是一个整数,在表内唯一。对于行 ID,TiDB 做了一个小优化,如果某个表有整数型的主键,TiDB 会使用主键的值当做这一行数据的行 ID。

每行数据按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{TableID}_recordPrefixSep{RowID}
Value: [col1, col2, col3, col4]

其中 tablePrefixrecordPrefixSep 都是特定的字符串常量,用于在 Key 空间内区分其他数据。其具体值在后面的小结中给出。

3.1.2 索引数据和 Key-Value 的映射关系

TiDB 同时支持主键和二级索引(包括唯一索引和非唯一索引)。与表数据映射方案类似,TiDB 为表中每个索引分配了一个索引 ID,用 IndexID 表示。

对于主键和唯一索引,我们需要根据键值快速定位到对应的 RowID,因此,按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: RowID

对于不需要满足唯一性约束的普通二级索引,一个键值可能对应多行,我们需要根据键值范围查询对应的 RowID。 因此,按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}
Value: null

3.1.3 映射关系小结

最后,上述所有编码规则中的 tablePrefixrecordPrefixSepindexPrefixSep 都是字符串常量,用于在 Key 空间内区分其他数据,定义如下:

tablePrefix     = []byte{'t'}
recordPrefixSep = []byte{'r'}
indexPrefixSep  = []byte{'i'}

另外请注意,上述方案中,无论是表数据还是索引数据的 Key 编码方案,一个表内所有的行都有相同的 Key 前缀,一个索引的所有数据也都有相同的前缀。这样具有相同的前缀的数据,在 TiKV 的 Key 空间内,是排列在一起的。因此只要小心地设计后缀部分的编码方案,保证编码前和编码后的比较关系不变,就可以将表数据或者索引数据有序地保存在 TiKV 中。采用这种编码后,一个表的所有行数据会按照 RowID 顺序地排列在 TiKV 的 Key 空间中,某一个索引的数据也会按照索引数据的具体的值(编码方案中的 indexedColumnsValue )顺序地排列在 Key 空间内。

3.1.4 Key-Value 映射关系的一个例子

最后通过一个简单的例子,来理解 TiDB 的 Key-Value 映射关系。假设 TiDB 中有如下这个表:

CREATE TABLE User {
	ID int,
	Name varchar(20),
	Role varchar(20),
	Age int,
	PRIMARY KEY (ID),
	KEY idxAge (Age)
};

假设该表中有 3 行数据:

1, "TiDB", "SQL Layer", 10
2, "TiKV", "KV Engine", 20
3, "PD", "Manager", 30

首先每行数据都会映射为一个 (Key, Value) 键值对,同时该表有一个 int 类型的主键,所以 RowID 的值即为该主键的值。假设该表的 TableID 为 10,则其存储在 TiKV 上的表数据为:

t10_r1 --> ["TiDB", "SQL Layer", 10]
t10_r2 --> ["TiKV", "KV Engine", 20]
t10_r3 --> ["PD", "Manager", 30]

除了主键外,该表还有一个非唯一的普通二级索引 idxAge,假设这个索引的 IndexID 为 1,则其存储在 TiKV 上的索引数据为:

t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

希望通过上面的例子,读者可以更好的理解 TiDB 中关系模型到 Key-Value 模型的映射规则以及选择该方案背后的考量。