KV 数据结构极大地简化了存储引擎的接口和实现. 基本的 KV 接口一般就是 Get(), Set(), 实现上代码也很简单, 极简的实现可以直接利用编码语言提供的 map(哈希, 红黑树)来提供内存数据结构, 而且硬盘上直接 dump 内存数据即可(类似 Redis 的策略).
不过, KV 存储引擎自己省事了, 但使用者不喜欢, 因为大部分的业务并不是 KV 所能表达的, 业务需要丰富的数据结构, 表格(table), 列表(list), map 等各种容器. 另外还需要排序功能, 业务依赖排序.
当前比较流行的 KV 存储引擎如 LevelDB, RocksDB, 因为其数据是 key 有序的, 所以许多结构化数据库引擎都基于其开发. 大家的思路都是使用 LevelDB 作为底层的持久化存储引擎, 通过在 key 上面做文章来实现丰富的数据结构支持. 类似的数据库有:
* SSDB, 兼容 Redis 数据结构
* tidb, 分布式关系数据库, 支持 SQL
* MyRocks, FaceBook 开源的 MySQL 引擎
SSDB 应该是最先开创在 KV 存储引擎之上建立结构化数据库的项目, SSDB 在 2012 年就使用这种模式开发并开源了生产环境使用的数据库.
在 KV 存储引擎之上建立数据结构, 关键点是利用其数据的有序性, 实现方式是巧妙地设计 key 以及数据冗余来表达数据结构. 例如 map 集合结构, 就可以这样在 LevelDB 上设计 key 的结构:
* 集合的 size: key = "map" + $name + "size", value = $size
* 集合的 pair: key = "map" + $name + $key, value = $value
而 SSDB 的 zset(SortedSet) 就相对复杂一些:
* 集合的 size: key = "zset" + $name + "size", value = $size
* 集合的元素按 score 排序: key = "zset_score" + $name + $score" + $item, value = ""
* 集合的元素按 item 排序: key = "zset_item" + $name + $item, value = $score
像 tidb 和 MyRocks 这样的关系数据库, 要实现表结构也并不更加复杂, 只是可能要存储事多的信息:
* 表的 meta 信息
* 主键索引: key = "PK" + $table + $PK, value = json_encode($row)
* 普通索引: key = "NK" + $table + $col + $PK, value = ""
* 更多的普通索引
可以看到, 主键索引是聚簇的, 其它索引带有主键的信息, 类似 innodb.