可插入式索引键列的实现方案咨询

需求梳理 #

• 能在任意两个相邻键值之间插入新数据
• 键为唯一键，可用于getByKey、deleteByKey这类数据操作
• 键支持比较操作（比如判断是否处于两个指定键之间）

已尝试方案的问题 #

1. 自增主键：完全无法满足中间插入需求，直接排除
2. VARCHAR分层键：通过字符串后缀扩展实现插入，但需自行维护生成逻辑（查重、位数扩展等），还要处理线程安全问题，复杂度太高
3. 多列方案：暂未找到简洁可行的实现方式

可行解决方案 #

1. 浮点型索引键（最简易） #

• 操作逻辑：插入新数据时，直接取前后两个键的中间值作为新键。比如在20和21之间插入，用20.5；在20和20.5之间插入，用20.25，以此类推。
• 优势：无需编写复杂生成逻辑，数据库原生支持唯一约束和比较操作，线程安全由数据库事务保证。
• 注意点：浮点型存在精度上限，当插入次数过多导致精度不足时，可切换为DECIMAL类型，或批量调整部分键值重新分配空间。

2. 有序UUID方案 #

• 操作逻辑：使用时间有序UUID（如UUIDv1、UUIDv6），这类UUID前缀包含时间戳，天然具备有序性。若业务允许按时间顺序插入，直接生成新UUID即可；若需在指定两个键之间插入，可解析前后UUID的二进制值，生成中间UUID。
• 优势：UUID本身自带唯一性，数据库支持对UUID的索引和比较，无需手动维护唯一逻辑。
• 注意点：在指定两个键之间插入时，需处理UUID的二进制解析，逻辑比浮点型稍复杂，但远优于VARCHAR方案。

3. 简洁版多列组合键 #

• 操作逻辑：采用(分组键, 序列值)的组合唯一键，序列值使用浮点型。插入时，在同一分组下取前后序列值的中间值；当序列值精度不足时，拆分分组键并重新分配序列值。比如原分组为g1、序列值20和21，插入中间值用20.5；当20.5和21之间插满时，将g1拆分为g1a和g1b，把原20.5到21的数据移至g1b并重置序列值。
• 优势：能缓解浮点型精度不足的问题，逻辑相对可控。
• 注意点：需维护组合键的唯一性，查询时需同时使用两列进行比较。

4. 数据库原生分层类型（如PostgreSQL的ltree） #

• 操作逻辑：若使用PostgreSQL，直接利用ltree类型，它天生支持分层有序结构，还自带比较、插入的原生函数。比如原键是20、21，插入中间值可设为20.1、20.2，再插入则用20.1.1，数据库会自动处理排序和唯一性约束。
• 优势：无需自行编写生成逻辑，数据库原生支持，性能有保障。
• 注意点：仅适用于支持ltree的数据库，通用性有限。

内容的提问来源于stack exchange，提问作者Hi computer