熊崎 宏樹:「明示的な削除」というのは語が不適切かと思います。少なくともデータベースのユーザーには削除されたかのように見せかけるはずで、それはある意味で明示だからです。ですから僕であれば「ユーザからは見えなくなるのが論理削除」と「データとして消失させるのが物理削除」という言葉で使い分けます。データベースより上のレイヤーでも削除フラグ列を用意してそのフラグが立っていたらその行は無かったことにするという論理削除テクニックともややこしくなるのが難点ですが、以下ではデータベース以下のレイヤーの話をします。 並行プログラムを書く際に、データの更新は研究が多く積まれており様々な並行制御プロトコルが提案されていますが揃って鬼門としているのがデータの挿入と削除です。例えばトランザクション内で物理削除してしまったレコードはトランザクションアボート時に物理的に挿入し直す必要があり、そこに別のトランザクションが割り込んで新規挿入しにきたらどうすべきでしょうか？アボートをアボートするわけには行かないので新規挿入の方を止める必要があり、そのロジックを実装するにはトランザクションが終わるまでの間はプレースホルダのような役割の物が挿入禁止として場所を守っている必要があります。データベースのロジックを簡潔かつ堅実なものとするために使うこのテクニックはGhost Recordと呼ばれ、例えばSQL Serverの内部では定期的に巡回して不必要なGhost Recordを消すワーカーがいます[ghost cleanup process guide]。 また詳説データベースはLSM(Log Structured Merge)-Treeに力を入れて解説している本で7章がまるごとログ構造化ストレージの話をしています。これはランダム書き込みの速度に重点を置いたデータ構造で、データの削除は「削除マークを書き込む」という形で実装しています。データファイル上で物理削除することはその気になればできるのですが、例えば典型的にはデータファイルはキーの昇順で並んだSSTable(Sorted String Table)だったりするので参照する側が二分探索できる状態を保つには消した分の領域を切り詰める処理が必要でそれはファイルサイズに比例する作業コストがかかります。ですので実際の実装ではLSM-Treeのデータファイルは不変であり、追加のデータファイルとマージした後に捨てられ、マージ操作の中で削除マークとマージさせられたレコードはマージ後ファイルからは消失する、という形で削除を管理しています。こちらのほうが参照のコストを引き上げずにディスクの負荷を抑えることができます。