ヒープファイルとテーブルアクセスメソッドの内部

ヒープとは何か――順序を持たない表の置き方

リレーショナル DB の表は、論理的には行の集合ですが、物理的には何らかのファイル編成でディスク上に並びます。最も基本的なのがヒープファイル（heap file）です。ヒープとは「行を特定の順序で並べず、入る場所に入れていく」非整列の集まりを指します。データ構造のヒープ（優先度付きキュー）とは無関係で、「がらくたを山積みにした状態」という語感に近いものです。

PostgreSQL・Oracle・SQL Server（既定）などはテーブル本体をヒープとして持ち、インデックスはそれとは別の B+Tree として独立に置きます。行の物理位置は挿入順とフリースペースの都合だけで決まり、列の値とは無関係です。だからこそ「キー順に物理整列される」クラスタ化インデックスとは対照的で、ヒープ自体には順序がない代わりに、どのインデックスからも公平な距離で参照できます。

ページ内レイアウト――スロット化ページ

ヒープは固定サイズのページ（PostgreSQL なら 8KB）の連なりです。各ページは可変長のタプルを格納するため、スロット化ページ（slotted page）という巧妙な配置を採ります。1ページの中身は3つの領域に分かれます。

ポインタ配列は前から、タプル本体は後ろから伸び、両者が出会った地点が満杯です。この設計の要点は、タプルを直接アドレスで指さず、必ず行ポインタ（line pointer / item ID）を経由して指すことにあります。間接参照を1段挟むことで、ページ内でタプルを物理的に動かしても（後述の VACUUM による空き詰めなど）、外部のアドレスを書き換えずに済みます。ポインタの番号さえ保てば、本体はページ内のどこに移しても構いません。

8KB ページの内部（概念図）
+----------------------------------------------------------+
| ヘッダ | LP1 | LP2 | LP3 |→  ……空き……  ←| tup3 | tup2 | tup1 |
+----------------------------------------------------------+
  LP（行ポインタ）は前から、タプル本体は後ろから詰める。
  LP2 = (offset, length) でページ内の tup2 を指す。

TID――行の物理アドレス

ヒープ上の1タプルを一意に指す住所が TID（Tuple Identifier、別名 CTID）です。TID は (ブロック番号, スロット番号) の2要素からなります。ブロック番号はヒープファイル内のページ番号、スロット番号はそのページの行ポインタ配列の何番目か、を表します。SQL Server や Oracle の RID（Row Identifier）も同じ発想で、「何番ページの何番スロット」を符号化したものです。

TID が重要なのは、インデックスの葉が指す先がこの TID だからです。セカンダリインデックスを下って葉に着くと、そこには列値ではなく TID が入っており、その TID でヒープを1回ランダム参照して行本体を得ます。この二段参照の仕組みはクラスタ化／非クラスタ化インデックスの内部差で詳述しています。逆に言えば、TID が安定して同じ行を指し続けることが、インデックスの整合性の前提になります。

空き領域マップ（FSM）――INSERT の置き場所を即決する

新しい行を INSERT するとき、DB は「十分な空きがあるページ」を探さねばなりません。全ページを順に調べていては表が大きいほど INSERT が遅くなります。これを避ける索引が空き領域マップ（Free Space Map, FSM）です。

FSM は各ヒープページの空きバイト量を粗い分解能（PostgreSQL ではページ1枚あたり1バイト＝256段階、約32バイト刻みの線形な区分）で記録し、それを木構造で持ちます。各ノードが配下の最大空き量を保持するので、「Nバイト以上空いているページ」を根から下りながら対数時間で1つ見つけられます。FSM 自体もヒープと並ぶ別ファイルで、表の数百分の一程度と小さく、メモリに載りやすいのが利点です。

INSERT に必要な空き = タプル長 + 行ポインタ1個ぶん
1) FSM の根から「必要量以上の空きを持つページ」を探索（対数時間）
2) 見つかればそのページに追記、見つからなければ末尾に新ページを割り当て
3) 実際の残り空きで FSM のそのページのエントリを更新

可視性マップ（VM）――スキャンと VACUUM を加速する

MVCC では1行に複数バージョンが存在し、各タプルが「どのトランザクションから見えるか」は、タプルに刻まれた xmin／xmax（生成・削除トランザクション ID）と各トランザクションのスナップショットで決まります（MVCC の内部実装参照）。この可視性判定は1タプルごとに行う必要があり、コストがかかります。

可視性マップ（Visibility Map, VM）は、ヒープページ1枚につき2ビットを持つ別ファイルで、片方のビットが「このページ上の全タプルが、現在実行中・今後開始する全トランザクションから可視か（=未来のどのスナップショットでも見える、いわゆる all-visible）」を表します。このビットが立ったページは、個々のタプルの可視性チェックを丸ごと省けます。

VM が効く代表がインデックスオンリースキャンです。本来インデックスから TID を得たら可視性確認のためヒープを読みに行く必要がありますが、その TID のあるページの VM ビットが all-visible なら、ヒープを読まずにインデックスの値だけで結果を返せます。ヒープへのランダム参照を丸ごと省けるため、カバリングインデックスの効果が跳ね上がります。もう片方のビット（all-frozen）は VACUUM が「凍結済みで再走査不要」と判断する印で、トランザクション ID 周回（wraparound）対策の凍結 VACUUM が、変化のない巨大領域を読み飛ばすのに使われます。

シーケンシャルスキャン――インデックスを介さない走査

ヒープの最も素朴なアクセスがシーケンシャルスキャン（seq scan）です。ヒープファイルを物理的に先頭ページから順に読み、各ページの行ポインタ配列を辿って全タプルを取り出し、1件ずつ可視性を判定して、可視なものを実行エンジンへ返します。

for ページ p in ヒープの全ページ（物理順）:
    p をバッファプール経由で読む
    for 行ポインタ lp in p:
        if lp が使用中:
            tup = lp が指すタプル
            if MVCC 可視性判定(tup, スナップショット) が真:
                上位ノードへ tup を返す

物理順の読み出しなのでディスクはシーケンシャル I/Oになり、1ページ当たりの単価が安いのが特徴です。だから「表の大半の行が条件に合う」クエリでは、インデックスで TID を引いてヒープをランダム参照する二段参照より、ヒープを丸ごと舐めるほうが速くなります。オプティマイザが選択率（条件に合う行の割合）を見てインデックスを捨て seq scan を選ぶのは、このシーケンシャル I/O ＜ ランダム I/O 連発という単価差が根拠です。

VACUUM とデッドタプル

MVCC では DELETE や UPDATE は古いバージョンを即時に消さず、誰からも見えなくなったデッドタプルとして残します。これを回収するのが VACUUM です。VACUUM はヒープを走査してデッドタプルの行ポインタを解放し、FSM に空き量を反映し、ページが all-visible になれば VM ビットを立てます。回収を怠るとデッドタプルがページを占有し続け（テーブル肥大化, bloat）、seq scan が読む無駄ページが増え、ページ密度が下がって性能が落ちます。

VACUUM が触ったページや FSM・VM の更新もまた WAL に記録され、クラッシュ後に整合した状態へ復旧されます。ヒープの物理変更が安全に永続化される土台はWAL（先行書き込みログ）の仕組みにあります。

まとめ

ヒープファイルは「行を順不同で詰め、TID という物理アドレスで指す」だけの素朴な表構造ですが、その周りに3つの補助構造が効いています。FSM は INSERT の置き場所を全走査なしで即決し、VM は可視性判定とヒープ参照を丸ごと省いてインデックスオンリースキャンと凍結 VACUUM を加速し、スロット化ページの行ポインタは VACUUM がページ内でタプルを動かしても外部アドレスを壊さない自由を与えます。

インデックスを介さない物理走査の速さは、ページ密度・HOT 更新・VM ヒット率という地味な要素で決まります。索引側から TID を辿る二段参照の代償はクラスタ化／非クラスタ化インデックスの内部差を、可視性判定そのものの仕組みはMVCC の内部実装を参照してください。