[B! algorithm][btree] a2ikmのブックマーク

a2ikm id:a2ikm

algorithmとbtreeに関するa2ikmのブックマーク (2)

B-Tree by Java -- B木のすごく簡単な実例
【B木のすごく簡単な実例】 B木アルゴリズム(B-Tree algorithm)とは、ファイルシステムやデータベースの実装の基礎となる平衡探索木のアルゴリズムです。平衡探索木では、要素の検索・挿入・削除などの操作が、いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。何の工夫もしない単なる２分探索木では、挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、各種操作に \(O(n)\) の計算量が必要になる場合があります。例えば図1.のような場合、数字の入っている丸をノードと呼び、出発点となる最上位のノードを根と呼びます。左図の平衡探索木では、木の根である 4 から数えて 7 に到達するのに 3 個のノードをたどるだけで済みますが、右図のバランスの崩れた木の場合は、根の 1 から数えて 7 に到達するのに 7 個のノー
a2ikm 2019/09/20
btree

algorithm
リンク
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
a2ikm 2018/02/26
Programming

algorithm

db

btree
リンク
1