参照元の遅延更新について検討する

[s-yata]

概要

参照先の行が削除されたときは参照元を自動で更新する機能（ #71 ）について，現在は削除をするとすぐに参照元を更新するようになっています．

しかし，行を削除する度に参照元を即時更新するという仕様では，索引がなければ時間計算量は O(n) になってしまいます（n は参照元の行数）．
n が大きかったり，頻繁に行を削除したりするのであれば，索引がないと使い物になりません．

そこで，参照元を更新するタイミングを遅らせるという案があります．
方法としては，削除行をデフォルト値で埋めて再利用を禁止にし，参照元もそのままにしておきます．
削除行がある程度の量に達した時点で，参照元を更新し，削除行の再利用を許可します．
これなら，参照元の更新にかかる時間計算量は同じですが，実行頻度を大幅に減らすことが可能なので，平均の時間計算量は小さくすることができます．

制限事項

参照元の更新を遅らせることにより，以下のように制限が発生します．

• 行の再利用制限
  • 参照元を更新するまでは，削除行の再利用が禁止されます．そのため，削除で空いた行を指定して再利用するといったことが，できたりできなかったりします．
• NULL 判定の複雑化
  • 参照が NULL かどうかを確かめるには，参照先の行が削除されていないかどうかを確認しなければなりません．
• 参照ベクタの更新
  • 該当する参照を NULL もどきにすることしかできないため，該当する参照をベクタから取り除くことはできません．

[s-yata]

実装案

基本的な考え方は，削除した行をデフォル値で埋めて，参照元を更新するまで再利用を禁止するというものです．

実装するとなると，参照元を更新するタイミングや，削除行を再利用する方法が課題になりそうです．

• 参照元を更新するタイミング
  • 削除行の割合や数などに閾値を設定しておき，その閾値に達したタイミングが妥当でしょうか．
• 削除行の再利用方法
  • 参照元を更新した後で削除行が追加される可能性があるため，再利用できる削除行と再利用できない削除行を区別する方法が必要です．
  • 再利用可能な削除行の ID を配列などに保存しておくという案は単純で良いのですが，削除行が多くなるとメモリ消費が多くなるという欠点があります． ID 指定で再利用するのは苦手です．
  • 再利用可能かどうかを示すビットマップを保存するという案は，削除行が少ないと無駄が多くなりますが，削除業が多くなると効率的になります． ID 指定で再利用するのは得意です．