B-Tree by Java -- B木のすごく簡単な実装
B木(B-Tree)とは、 ファイルシステムやデータベースの実装の基礎となる平衡探索木です。 平衡探索木では、要素の検索・挿入・削除などの操作が、 いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に \(O(n)\) の計算量が必要になる場合があります。 データベースでは、B木の検索の計算量が \(O(\log n)\) であることを利用してインデックス(索引)を作ります。 インデックスを使うと、 通常の検索よりも速くデータにアクセス出来るようになります。 ちなみに、B木と同じ平衡探索木の 赤黒木 や AVL木 も各種操作の計算量は、いかなる場合でも \(O(\log n)\) ですが、 これらは２分木で実現されており、完全にはバラ
Oracleのインデックスのツリーのバランスが崩れる? — ありえるえりあ
Recent entries Apache2.4のリリース予定は来年(2011年)初め(あくまで予定) inoue 2010-12-23 Herokuの発音 inoue 2010-12-20 雑誌記事「ソフトウェア・テストPRESS Vol.9」の原稿公開 inoue 2010-12-18 IPA未踏のニュース inoue 2010-12-15 労基法とチキンゲーム inoue 2010-12-06 フロントエンドエンジニア inoue 2010-12-03 ASCII.technologies誌にMapReduceの記事を書きました inoue 2010-11-25 技術評論社パーフェクトシリーズ絶賛発売中 inoue 2010-11-24 雑誌連載「Emacsのトラノマキ」の原稿(part8)公開 inoue 2010-11-22 RESTの当惑 inoue 2010-11-22 「プ
B-treeインデックス入門 - Qiita
B-treeがMySQLで使用されている背景から、B-treeインデックスの構造、そしてそれに基づいたインデックスの使用方法の入門編です。以下の流れに沿ってまとめていきます。 インデックスってなに？ B-treeってなんでインデックスに使われているの？ B-treeインデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索を高速化することができます。 特定の項目が本のどこに載っているかを確認するために索引を調べることで、全ページを順に調べなくても、その項目が登場するページ番号がわかる MySQLのストレージエンジンでも、インデックスが同様の方法で利用されており、インデックスの
なぜBTreeがIndexに使われているのか - maru source
※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル CREATE TABLE user ( id INT UNSIGNED NOT NULL, name VARCHAR(255) NOT NULL, UNIQUE INDEX (id) ); idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています
B木 - Wikipedia
B木（びーき、英:B-tree）は、計算機科学におけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。 実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。 構造[編集] B木の例 多分岐の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる[2]。 各ノードは、枝の数 - 1 のキーを持つ。枝1 ～ 枝m と キー1 ～ キーm -1 を持つとき、枝i には キーi -1 より大きく キーi より小さいキーだけを保持する（
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
