B-Tree - ページ単位の入出力に合わせた索引の木
B-Tree は、1 つのノードに数百件のキーを並べることで、木の段数を数段に抑えた探索木です。ノードとは木を構成する 1 つの箱を指します。この構造が最もよく使われるのは、RDB(リレーショナルデータベース)の索引(インデックス)の実装です。CREATE INDEX で作る一般的な索引も、主キーや一意制約を支える索引も、多くは B-Tree 系の構造です。 ...
B-Tree は、1 つのノードに数百件のキーを並べることで、木の段数を数段に抑えた探索木です。ノードとは木を構成する 1 つの箱を指します。この構造が最もよく使われるのは、RDB(リレーショナルデータベース)の索引(インデックス)の実装です。CREATE INDEX で作る一般的な索引も、主キーや一意制約を支える索引も、多くは B-Tree 系の構造です。 ...
Index Scan は、索引(インデックス)を辿って条件に一致するレコードの在り処を求め、そこから表のレコードを読み出す方法です。DB(データベース)が 1 つの表からレコードを取り出す手段の 1 つで、表を先頭から順に読むシーケンシャルスキャン(sequential scan)と対になります。 ...
LSM-Tree(Log-Structured Merge-Tree)は、更新をメモリに貯めてから、キーの順に並べたファイルとしてディスクにまとめて書く索引です。同じキーを更新すると新しいバージョンを別のファイルに足し、古いバージョンは後から行うコンパクション(compaction)で捨てます。 ...
ページング(pagination)は、一覧の結果を 20 件ずつのように区切って返す仕組みです。SNS のタイムライン、管理画面の一覧、API の一覧取得など、件数が多い一覧のほとんどで使われます。SQL で書く方法は大きく 2 つあり、1 つは LIMIT 20 OFFSET 40 のように先頭から何件を飛ばすかを指定する OFFSET、もう 1 つは前のページの最後のレコードの値を覚えておき、その続きから読むキーセット(keyset pagination、seek method とも呼ばれる)です。 ...
UUID(Universally Unique Identifier)は、128 ビットの識別子です。DB(データベース)に問い合わせずにアプリ側で ID を作れること、複数の DB で作った ID が衝突しないこと、URL に出しても件数や順番が推測されにくいことから、表の主キーに使われます。一方で、「UUID を主キーにすると索引が遅くなる」という話もよく聞きます。 ...