ジンジャー研究室

長めのつぶやき。難しいことは書きません。

2つの順序キーの間のキーをいい感じに生成するライブラリを作った

RDB で ORDER BY するためのカラムを持つ時に、並び替えや挿入がうまく出来なくて困った。

f:id:jinjor:20180905182715p:plain

例えば、このテーブルで B と C の間に E を差し込みたい時に、

f:id:jinjor:20180905181617p:plain

こうなってくれると嬉しい。

作ったもの

🎉

github.com

TypeScript 用に書き直してくれてもいいのよ?

仕組み

  • キーは 0-9A-Za-z の 62 種類の文字が使える、ただし、最後の文字が 0 であってはいけない
  • 最初のキーは 1
  • 次のキーは「既存のキーの次」か「既存のキーの前」か「既存の2つのキーの間」のいずれかを指定して生成する
  • キーの左の桁を優先的にインクリメントしようとするが、無理な場合は桁を増やしてインクリメントする
  • 例:
    • between "1" "3" == "2"
    • between "1" "2" == "11"
    • between "1" "11" == "101"
    • after "1" == "2"
    • after "z" == "z1"
    • その他

技術的な話

Fuzzer を使って 10 万テストケースを自動生成して回しています。

今回は 0, 1, z などの境界値付近を重点的に攻めるために確率を操作しています

参考リンク: