入門 B-link tree
概要 DBMS で広く利用されている B+ tree には様々な variant が存在するが、B-link tree もその1つ。 シンプルなラッチプロトコルで並行アクセスをさばけるよう、リーフノード以外のノードにも右の隣接ノードへのポインタを持たせた構造となっており、PostgreSQL で使われていることでも有名。 この記事では主にこの B-link tree に焦点を当てる。 B+ tree 全般やその他インデックス技術自体に興味がある場合は「最強DB講義 #10 いまどきのデータベース索引技術（石川佳治 教授）」の講義資料を読むのがおすすめ。 B-link tree 理解する上で必須な知識「ラッチ」 「ラッチ」というのはいわゆるロックのことだが、DB においては「ロック」というとトランザクション分離のための高価な(数千CPUサイクルを要する)処理を指すことが多く、「ラッチ」という
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
PostgreSQLの共有バッファ(shared_buffer)とMySQLのバッファプール(buffer_pool)のメカニズム比較 - interdb’s blog
PostgreSQLとMySQLのバッファについて。 PostgreSQLのバッファマネージャ 詳細はこちらをみて頂くとして、PostgreSQLのバッファマネージャは、２００５年リリースのバージョン8.1で大幅に変わった。 以下の表をみて頂くとわかるようにページ置換アルゴリズムは、8.0まではリストで実装したLRUとそのバリエーションであったが、8.1から配列で実装したClockSweep方式になった。 ページ置換アルゴリズムとロックの変遷 バージョン ページ置換アルゴリズム バッファマネージャのロック 方式 説明 PostgreSQL での呼称 説明 7.4まで [〜2004] LRU "Least Recently Used"の略称。最もオーソドックスなアルゴリズム。 BufMgrLock 排他ロックのみ。ページの入れ替えだけでなく、読み取りでも排他ロックをかける*1。 8.0.0〜
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
