B-Tree - ページ単位の入出力に合わせた索引の木

B-Tree は、1 つのノードに数百件のキーを並べることで、木の段数を数段に抑えた探索木です。ノードとは木を構成する 1 つの箱を指します。この構造が最もよく使われるのは、RDB(リレーショナルデータベース)の索引(インデックス)の実装です。CREATE INDEX で作る一般的な索引も、主キーや一意制約を支える索引も、多くは B-Tree 系の構造です。 ...

2026年8月10日 · 更新: 2026年11月12日 · 18 分 · nchika

Index Scan - 索引から表のレコードに届くまでに何が起きるか

Index Scan は、索引(インデックス)を辿って条件に一致するレコードの在り処を求め、そこから表のレコードを読み出す方法です。DB(データベース)が 1 つの表からレコードを取り出す手段の 1 つで、表を先頭から順に読むシーケンシャルスキャン(sequential scan)と対になります。 ...

2026年8月11日 · 更新: 2026年11月12日 · 20 分 · nchika

LSM-Tree - 上書きせずに追記する索引とコンパクション

LSM-Tree(Log-Structured Merge-Tree)は、更新をメモリに貯めてから、キーの順に並べたファイルとしてディスクにまとめて書く索引です。同じキーを更新すると新しいバージョンを別のファイルに足し、古いバージョンは後から行うコンパクション(compaction)で捨てます。 ...

2026年11月10日 · 更新: 2026年11月14日 · 15 分 · nchika

Keyset Pagination - OFFSET が後ろのページほど遅くなる理由と、前のページの続きから読む方法

ページング(pagination)は、一覧の結果を 20 件ずつのように区切って返す仕組みです。SNS のタイムライン、管理画面の一覧、API の一覧取得など、件数が多い一覧のほとんどで使われます。SQL で書く方法は大きく 2 つあり、1 つは LIMIT 20 OFFSET 40 のように先頭から何件を飛ばすかを指定する OFFSET、もう 1 つは前のページの最後のレコードの値を覚えておき、その続きから読むキーセット(keyset pagination、seek method とも呼ばれる)です。 ...

2026年11月11日 · 更新: 2026年11月12日 · 15 分 · nchika

UUIDv7 - 時刻順に並ぶ UUID を主キーにすると、索引の何が変わるか

UUID(Universally Unique Identifier)は、128 ビットの識別子です。DB(データベース)に問い合わせずにアプリ側で ID を作れること、複数の DB で作った ID が衝突しないこと、URL に出しても件数や順番が推測されにくいことから、表の主キーに使われます。一方で、「UUID を主キーにすると索引が遅くなる」という話もよく聞きます。 ...

2026年11月11日 · 更新: 2026年11月12日 · 13 分 · nchika