2分探索木の考え方を拡張したもので、B木がある。
B木の構造
B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。
B木からデータの検索
データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(N) O(logN) 資料修正注意となる。
B木へのデータの追加
B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越えた場合は、以下のような処理を行う。
ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。
データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。
B木とデータベース
このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。
データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。
データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。
((リレーショナル・データベースの例)) STUDENT RESULT ID | name | grade | course ID | subject | point -----+----------+-------+-------- -----+---------+------- 1001 | t-saitoh | 5 | EI 1001 | math | 83 1002 | sakamoto | 4 | E 1001 | english | 65 1003 | aoyama | 4 | EI 1002 | english | 90 ((SQLの例)) select STUDENT.name , RESULT.subject , RESULT.point from STUDENT , RESULT where STUDENT.ID == RESULT.ID -- 串刺し -- and RESULT.point >= 60 ; ((上記SQLをC言語で書いた場合)) for( st = 0 ; st < 3 ; st++ ) for( re = 0 ; re < 3 ; re++ ) if ( student[ st ].ID == result[ re ].ID && result[ re ].point >= 60 ) printf( "%s %s %d" , student[ st ].name , result[ re ].subject , result[ re ].point ) ;
B+木
データベースの処理では、目的のデータを見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。
そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。
Wikipedia B+木 より引用