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) 键值对：

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

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

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

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

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

  1. Key:   tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
  2. Value: RowID

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

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

3.1.3 映射关系小结

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

  1. tablePrefix     = []byte{'t'}
  2. recordPrefixSep = []byte{'r'}
  3. indexPrefixSep  = []byte{'i'}

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

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

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

  1. CREATE TABLE User {
  2.     ID int,
  3.     Name varchar(20),
  4.     Role varchar(20),
  5.     Age int,
  6.     PRIMARY KEY (ID),
  7.     KEY idxAge (Age)
  8. };

假设该表中有 3 行数据：

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

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

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

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

  1. t10_i1_10_1 --> null
  2. t10_i1_20_2 --> null
  3. t10_i1_30_3 --> null

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