入門 B-link tree概要 DBMS で広く利用されている B+ tree には様々な variant が存在するが、B-link tree もその1つ。 シンプルなラッチプロトコルで並行アクセスをさばけるよう、リーフノード以外のノードにも右の隣接ノードへのポインタを持たせた構造となっており、PostgreSQL で使われていることでも有名。 この記事では主にこの B-link tree に焦点を当てる。 B+ tree 全般やその他インデックス技術自体に興味がある場合は「最強DB講義 #10 いまどきのデータベース索引技術（石川佳治 教授）」の講義資料を読むのがおすすめ。 B-link tree 理解する上で必須な知識「ラッチ」 「ラッチ」というのはいわゆるロックのことだが、DB においては「ロック」というとトランザクション分離のための高価な(数千CPUサイクルを要する)処理を指すことが多く、「ラッチ」という
