聊聊数据库主键那点事儿
B-Tree
OLTP 数据库（MySQL InnoDB、Oracle、SQLServer 等）中，表一般是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
作为最常用的索引数据结构，B-Tree 是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。如下图所示：
可以看到，所有数据记录都只存储在叶子节点上。每个叶子节点都引用了树中的下一条记录。数据库就可以通过使用索引来执行二分查找，快速定位数据。
单体数据库
自增主键
一般来说，多数设计规范都会要求，主键不要带有业务属性。从性能来存储空间方面考量，自增主键往往是更合理的选择。
写数据的性能成本
带有业务逻辑的字段做主键，一般不容易保证有序插入，写数据成本相对高。
参考上面的 B-Tree 数据结构，如果自增主键，因为新数据的 Key 是最大的，就是在表的尾部追加数据行，在磁盘层面即表现为顺序写。
但如果是其它数据类型，比如字符串，因为树上的数据是有序的，所以就需要先在树上找到能插入数据的位置，然后才能插入数据，在磁盘层面就需要随机写了。
磁盘的随机读写与顺序读写性能相差两三个数量级（SSD 例外，相差不大）。
更糟的情况，比如 MySQL、SQLServer 因为数据是以数据页结构存储在磁盘上，如果要插入数据的位置的数据页已满，就要申请一个新的数据页，然后挪动部分数据过去，是为数据页分裂。Oracle 类似的索引块满了就会有发生索引分裂。
存储空间
不同于 Oracle 的 rowid，MySQL、SQLServer 的每个非主键索引的叶子节点上存的是主键的值。如果用比如身份证号或学号这样的字符串做主键，那非主键索引的叶子节点要占用 10 几个，20 个字节，如果是自增主键，整型是 4 个字节，长整型是 8 个字节。
业务字段做主键场景
并非所有场景都合适使用自增主键。
Key-Value 场景，一般最常见的就是配置表。查询时用 Key 查询，也不存在二级索引的情况，就不适合使用自增主键了。
分布式数据库
自增主键的特性无法保证
在单体时代，或者非高并发的场景，自增主键完全够用。
在分布式，海量并发的场景下，自增主键的基本特性就无法保证了。
无法连续递增
当事务发生冲突时，主键就会跳跃，留下空洞。
不限于分布式数据库，单体数据库也存在无法连续递增的场景：
与并发无关，事务回滚会导致空洞。
批量插入数据时的批量分配也有可能浪费而产生空洞。
也就是说即使在单体数据库场景下也是无法保证连续递增的，也所以拿最大的自增主键值作为表记录行数使用是不精确的。
无法单调递增
高并发场景下，自增主键的访问会成为性能瓶颈。常见的方案是高低位组合生成主键，数据库生成高位，低位由应用生成，比如高位返回“12345”，低位“00001”，组合后“1234500001”。但这样就无法保证单调递增了。
自增主键 + Range 分片问题
如果同时使用自增主键 + Range 分片，那新增加的数据就都集中在了一个 Range 分片范围内了，整个集群退化为了单机的写入性能，单机热点，也就没有集群的读写优势了。
分布式数据库主键方案
UUID
是的，没看错，就是单体时代很多人喜欢使用的 UUID。
优点是使用简单方便。
缺点很明显，那就是键值长度过长，达到了 128 位，转成字符串就是 32 个长度，因此存储和计算的代价都会增加。
Random ID
TiDB 模仿 MySQL 的 AutoIncrement，提供了 AutoRandom 关键字用于生成一个随机 ID 填充指定列。
随机 ID 是一个 64 位整数，主要由事务开始时间+自增的序号组成。
Snowflake
雪花算法是 Twitter 公司分布式项目的 ID 生成算法，64 位整数。四个部分组成：符号位、时间戳、机器 ID、序列。
支持的 TPS 可以达到 419 万左右。
别忘了 NTP 时钟回拔问题就要在算法里稍处理一下。
参考资料
MySQL 实战 45 讲（极客时间）
分布式数据库 30 讲（极客时间）
https://dzone.com/articles/database-btree-indexing-in-sqlite
https://docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT1170
版权声明: 本文为 InfoQ 作者【Steven】的原创文章。
原文链接:【http://xie.infoq.cn/article/cd13860f9cfd1b1f7b489fe52】。文章转载请联系作者。
还未添加个人签名 2008-07-18 加入
还未添加个人简介
评论