キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
Cache-Oblivious データ構造入門 @DSIRNLP#5
9. なぜ B-Tree の方が良いか？ 大事な前提（若干雑） 1. ディスクの読み込み時間 >> 計算時間 2. ディスクである箇所を読み込むと周辺も含 めてそこそこ大きく読まれる 前提より • ディスクを読み込む回数だけを考える – 普段の議論：「O(ほげ) 時間」 – 今回の議論：「ディスクI/O 𝑂(ほげ) 回」 • 一度に読み込まれるサイズを 𝐵 とおく Cache-Oblivious データ構造入門 (@iwiwi) 10 10. データの探索にかかる I/O 回数 二分探索木 • 𝑂 log 𝑛 回 一回の I/O で 2 分岐 B-Tree • 𝑂 log 𝐵 𝑛 回 一回の I/O で Θ(𝐵) 分岐！ ↑ノードのサイズをブロックサイズ 𝐵に合わせる B-Tree のほうが log 𝐵 倍ぐらい早い これは平気で 10 倍とかになるので大違い！ Cac
B+Trees and why I love them, part I - Ayende @ Rahien
One of the things that I enjoy about learning new things is the way it changes the way I look at the stuff that I already knows. Reading the LMDB codebase, and implementing a persistent B+Tree has given me a new depth of understanding about how relational databases (and Esent, too), work. I am going to go back to level zero and assume that you have never heard about this. You probably know what a
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
RDBMSで使われるB木を学ぼう （1/3）－ ＠IT
第5回 RDBMSで使われるB木を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/6/22 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第3回「AVL木で木構造を学ぼう」、第4回「もっとAVL木で木構造を学ぼう」と2回連続でAVL木について解説しました。 今回はAの後だからBというわけではありませんが、B木（B-Tree）を取り上げます。 B木の変種であるB+木やB*木は、OracleやPostgreSQL、Firebirdなどのリレーショナルデータベースでインデックスとして利用されている、メジャーな木構造です。 筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
