[B! btree] msyktのブックマーク

なぜ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とはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています

msykt 2019/08/18

“ブロックの読み取り回数は木の深さ(探索回数t)になります。 BTreeの場合log N / log m、二分探索木の場合log Nになります。これはmが大きくなればなるほど、差が出てきます。”

btree

リンク

B+Tree index structures in InnoDB

msykt 2013/01/16

リンク

B+Tree in Ruby

B+Tree And Ruby 以前、java.util.MapをBSONでファイルに保存するFileStoredMapというコレクションクラスを書きました。今度はそれのTree版を書こうと考えたのですが、Tree自体をこれまでロクに書いたことが無かったので、まずはRubyでB+Treeを書いてみました。こういった作って動かしてみてどういうものか確認するのは、スクリプト言語の方が楽なので。実際、動かしながら作っていくのはなかなか面白い作業でした。 b_plus_tree.rb: 1class AbstractNode 2 @@root = nil 3 4 def initialize(n, keys, parent) 5 @slot = n 6 @keys = keys 7 @parent = parent 8 @@root = self unless @@root 9 end 10 1

msykt 2012/08/09

RubyでB+Treeを書いてみた

ruby
btree

リンク

Oracle の B*Tree インデックスの内部構造についてお勉強中（その１）

お仕事のデータベース一式のリース切れ間近ということで、リース延長で耐えることができるのか、それともシステム更改が必要なのかを見極めるため、最近はデータベース周りのチューニングばかりやってます。当初設計時に、５年間持つ設計をしたのですが、流石に５年目にもなると予定とはそれなりに乖離が発生するものです。テーブル＆インデックス設計をユーザ向けの処理をとにかく高速に処理できるように設計したので、ユーザ向けの処理は速度的に全然大丈夫なのですが、データの肥大化によるバッチ処理のパフォーマンス劣化が顕著です。単純にストレージと CPU パワーが足りていないのでしょう。しかしながらチューニングの余地はまだまだ十分にありそうです。バッチ向けの最適化を図ることにしました。うまくいけば来年度どころか、後数年はリース延長で延命できるかもしれません。今回実施したチューニングの１つのポイントとして、バッチ処理向

msykt 2012/02/12

oracle
btree

リンク

saving Btrees to a disk file and read it

msykt 2012/02/11

btree

リンク

開発メモ: オンメモリB+木による省メモリ連想配列

Kyoto Cabinet 1.2.2から加わったGrassDBは、オンメモリでページ管理を行うB+木を実装してメモリを節約しちゃう仕組みである。それを使ってJava、Python、Ruby、Perlなどのハッシュ（連想配列）機構を鬼のように省メモリにしてみる。頑張ればなんと20分の1になる。前提 B木やその変種のB+木などは、キーの順序が近いレコード群を「ページ」という単位にまとめてシリアライズしてストレージに書き込むことで、入出力の頻度を減らして高速化することを意図している。メモリに比べて低速なストレージの上で大量のデータを管理するために使われる。多くのRDBMSやいくつかのDBMがB+木をサポートしているのはそれが理由であろう。一方で、メモリ上で検索可能なデータ構造を表現するためには、二分探索木やその特殊例である赤黒木が使われる。STLのstd::mapの実装にも赤黒木を使うのが一