第5回 RDBMSで使われるB木を学ぼう

2009/6/22

B木のテストプログラム

　今回も、B木の様子がわかるようなテストプログラムを作成しました。既定値では、次数が2のB木が生成されるようになっていますが、右側のSpinEditで次数を指定して「K次のB木を生成」ボタンをクリックすれば、K次のB木が内部に作成されます。

　「キーの追加」ボタンでは指定したキーを追加できます。また、「ランダムにn個追加」でn個のキーをB木に追加してその様子を見られるようにもしました。次数が変わると木の成長の速度も変わりますので、この辺を実際に見ながら確認するとよりイメージが湧くのではないかと思います。

●BTreeのソースコード（BTree.pas）

[全文を別ページで開く]

001: unit BTree;
002: 
003: interface
004: 
005: uses
006:   SysUtils, Classes, StrUtils, Dialogs;
007: 
008: type
009: 
010:   TKeyVal = record
011:     Key: Integer;
012:     Val: Integer;
013:   end;
014: 
015:   TBTreeNode = class(TObject)
016:   private
017:     FCount: Integer;
018:     FMaxKeys: integer;
019:     FKeys: array of Integer;
020:     FVals: array of integer;
021:     FChildNodes: array of TBTreeNode;
022:     FOrder: integer;
023:     function GetChildNodes(Index: Integer): TBtreeNode;
024:     function GetKeys(Index: Integer): Integer;
025:     function GetVals(Index: Integer): Integer;
026:     procedure InsertKeyVal(Index: Integer; const new_key, new_val: Integer);
027:     procedure InsertChildNode(Index: Integer; const new_node: TBtreeNode);
028:     procedure SetChildNodes(Index: Integer; const Value: TBtreeNode);
029:     procedure SetKeys(Index: Integer; const Value: Integer);
030:     procedure SetVals(Index: Integer; const Value: Integer);
031:     function IsLeaf:Boolean;
032:   protected
033:     procedure DumpNodes(var S : String; depth : Integer);
034:     function InternalAdd(new_key, new_val:Integer; var new_node:TBtreeNode;var return_key, return_val:Integer):boolean;
035:     procedure SetCount(Value : Integer);
036:   public
037:     constructor Create(Order:Integer);
038:     destructor  Destroy;override;
039:     property Order    : Integer read FOrder;
040:     property MaxKeys  : Integer read FMaxKeys;
041:     property Keys[Index:Integer]:Integer read GetKeys write SetKeys;
042:     property Vals[Index:Integer]:Integer read GetVals write SetVals;
043:     property ChildNodes[Index:Integer]:TBtreeNode read GetChildNodes write SetChildNodes;
044:     property Count:Integer read FCount;
045:   end;
046: 
047:   TBtree = class(TObject)
048:   private
049:     FCount : Integer;
050:     FOrder : Integer;
051:     FRoot  : TBTreeNode;
052:   protected
053:   public
054:     function DumpNodes:String;
055:     procedure Add(new_key, new_val:Integer);
056:     constructor Create(Order:Integer);
057:     destructor Destroy;override;
058:     property Order : Integer read FOrder;
059:     property Count : Integer read FCount;
060:   end;
061: 
062: implementation
063: 
064: { TBTreeNode }
065: 
066: //節点のコンストラクタ
067: constructor TBTreeNode.Create(Order:Integer);
068: begin
069:   inherited Create;
070: 
071:   FCount    := 0;
072:   FOrder    := Order;
073:   FMaxKeys  := Order * 2;
074: 
075:   //実装を簡易にするため、0..2*K、つまり要素数2K+1の配列とする
076:   SetLength(FKeys, FMaxKeys + 1);
077:   SetLength(FVals, FMaxKeys + 1);
078: 
079:   //子節点へのリンクは2K+1個を使用するので、余分を1つとる
080:   //こうしておくと、分割の際に、K+1個ずつ分配しやすい
081:   SetLength(FChildNodes, FMaxKeys + 2);
082: 
083: end;
084: 
085: //節点のデストラクタ
086: //子節点があれば、それを解放する
087: destructor TBTreeNode.Destroy;
088: var
089:   idx : Integer;
090: begin
091:   for idx := 0 to FCount do
092:   begin
093:     if (FChildNodes[idx] <> nil) then FChildNodes[idx].Free;
094:   end;
095: 
096:   inherited;
097: end;
098: 
099: //節点の状態を返す処理
100: procedure TBTreeNode.DumpNodes(var S: String; depth: Integer);
101: var
102:   idx : Integer;
103: begin
104:   //節点が葉かどうかで処理を分ける
105:   if (IsLeaf = True) then
106:   //葉である場合
107:   begin
108:     for idx := 0 to FCount -1 do
109:     begin
110:       S := S + DupeString('  ', depth) + IntToStr(FKeys[idx]) + #13#10;
111:     end;
112:   end else
113:   //葉でない場合
114:   begin
115:     for idx := 0 to FCount -1 do
116:     begin
117:       FChildNodes[idx].DumpNodes(S, depth + 1);
118:       S := S + DupeString('  ', depth) + IntToStr(FKeys[idx]) + #13#10;
119:     end;
120:     FChildNodes[FCount].DumpNodes(S, depth + 1);
121:   end;
122: end;
123: 
124: function TBTreeNode.GetChildNodes(Index: Integer): TBtreeNode;
125: begin
126:   result := FChildNodes[Index];
127: end;
128: 
129: function TBTreeNode.GetKeys(Index: Integer): Integer;
130: begin
131:   result := FKeys[Index];
132: end;
133: 
134: function TBTreeNode.GetVals(Index: Integer): Integer;
135: begin
136:   result := FVals[Index];
137: end;
138: 
139: //節点への要素の追加
140: function TBTreeNode.InternalAdd(new_key, new_val:Integer; var new_node:TBtreeNode;var return_key, return_val:Integer):boolean;
141: var
142:   idx : Integer;
143: begin
144:   //新しいキーがバケット内のどの位置にあたるかをチェックしておく
145:   //idxには、new_key の位置が入る
146:   if (FCount = 0) then
147:     idx := 0
148:   else
149:     for idx := 0 to FCount - 1 do
150:       if (FKeys[idx] > new_key) then break;
151: 
152:   //葉の場合とそうでない場合で処理を分ける
153:   if (IsLeaf = True) then
154:   //節点が葉である場合
155:   begin
156:     //新しいキーより大きい値の左側へ新しいキーを挿入する
157:     //余分を1つ取ってあるので必ず挿入できる
158:     InsertKeyVal(idx, new_key, new_val);
159: 
160:     //すでにバケットがいっぱいかどうかで処理を分ける
161:     if (FCount > FMaxkeys) then
162:     begin
163:       //バケットの分割が発生する
164:       result := True;
165: 
166:       //分割用の新しい節点を生成
167:       new_node := TBTreeNode.Create(FOrder);
168: 
169:       //新節点へ値を移動する
170:       for idx := 0 to FOrder - 1 do
171:       begin
172:         //中央値はK番目にあたるので、K+1番目から上を新節点へ移動
173:         //(K-1)+(K+1)=2K
174:         new_node.Keys[idx] := FKeys[idx + FOrder + 1];
175:         new_node.Vals[idx] := FVals[idx + FOrder + 1];
176:       end;
177: 
178:       //親節点へ返すキーと値の組をセット
179:       return_key := FKeys[FOrder];
180:       return_val := FVals[FOrder];
181: 
182:       //分割によって、CountはKになる
183:       FCount := FOrder;
184:       new_node.SetCount(FOrder);
185: 
186:       exit;
187:     end else
188:     begin
189:       //分割は発生していない
190:       result := False;
191:       exit;
192:     end;
193:   //節点が葉で無い場合の処理
194:   end else
195:   begin
196:     //新しいキーより大きいキーの左側の子節点へキーを追加する
197:     //idxには、キーの位置が入っているので、同じ位置のFChildNodesがそれにあたる
198: 
199:     //追加した結果分割が発生したかどうかで処理を分ける
200:     if (FChildNodes[idx].InternalAdd(new_key, new_val, new_node, return_key, return_val) = True) then
201:     //分割が発生した
202:     begin
203:       //分割の結果返されたキーを挿入するのも、idxの位置になるので
204:       //これを再度チェックする必要はない
205: 
206:       //新しいキーより大きい値の左側へ新しいキーを挿入する
207:       //余分を1つ取ってあるので必ず挿入できる
208:       InsertKeyVal(idx, return_key, return_val);
209: 
210:       //新しい子節点を追加する
211:       //位置としては、右側の子節点となるので、idx+1の位置へ挿入する
212:       InsertChildNode(idx + 1, new_node);
213: 
214:       //すでにバケットがいっぱいかどうかで処理を分ける
215:       if (FCount > FMaxkeys) then
216:       begin
217:         //バケットの分割が発生する
218:         result := True;
219: 
220:         //分割用の新しい節点を生成
221:         new_node := TBTreeNode.Create(FOrder);
222: 
223:         //新節点へ値を移動する
224:         for idx := 0 to FOrder - 1 do
225:         begin
226:           //中央値はK番目にあたるので、K+1番目から上を新節点へ移動
227:           //0+K+1=K+1 ～ (K-1)+(K+1)=2K を移動する
228:           new_node.Keys[idx] := FKeys[idx + FOrder + 1];
229:           new_node.Vals[idx] := FVals[idx + FOrder + 1];
230: 
231:           //子節点へのリンクも同様に移動し、移動元をnilで埋める
232:           new_node.ChildNodes[idx] := FChildNodes[idx + FOrder + 1];
233:           FChildNodes[idx + FOrder + 1] := nil;
234:         end;
235: 
236:         //子節点へのリンクは、一番右側がはみ出すのでこれを移動する
237:         new_node.ChildNodes[FOrder] := FChildNodes[FMaxKeys + 1];
238:         FChildNodes[FMaxKeys + 1] := nil;
239: 
240:         //親節点へ返すキーと値の組をセット
241:         return_key := FKeys[FOrder];
242:         return_val := FVals[FOrder];
243: 
244:         //分割によって、CountはKになる
245:         FCount := FOrder;
246:         new_node.SetCount(FOrder);
247: 
248:         exit;
249: 
250:       end else
251:       //分割は発生していない
252:       begin
253:         result := False;
254:         exit;
255:       end;
256:     end else
257:     //分割が発生していない
258:     begin
259:       result := False;
260:       exit;
261:     end;
262:   end;
263: end;
264: 
265: function TBTreeNode.IsLeaf: Boolean;
266: begin
267:   result := (FChildNodes[0] = nil);
268: end;
269: 
270: procedure TBTreeNode.SetChildNodes(Index: Integer; const Value: TBtreeNode);
271: begin
272:   FChildNodes[index] := Value;
273: end;
274: 
275: procedure TBTreeNode.SetCount(Value: Integer);
276: begin
277:   FCount := Value;
278: end;
279: 
280: procedure TBTreeNode.SetKeys(Index: Integer; const Value: Integer);
281: begin
282:   FKeys[Index] := Value;
283: end;
284: 
285: //Indexを指定した位置に、ChildNodeを挿入する
286: procedure TBTreeNode.InsertChildNode(Index: Integer;
287:   const new_node: TBtreeNode);
288: var
289:   idx : Integer;
290: begin
291:   //追加するキーのために場所を確保する
292:   for idx := FCount + 1 downto index + 1 do
293:   begin
294:     FChildNodes[idx] := FChildNodes[idx - 1];
295:   end;
296: 
297:   FChildNodes[index] := new_node;
298: 
299: 
300: end;
301: 
302: //Indexを指定した位置に、キー＝Valueを挿入する
303: procedure TBTreeNode.InsertKeyVal(Index: Integer; const new_key, new_val: Integer);
304: var
305:   idx : Integer;
306: begin
307: 
308:   //追加するキーのために場所を確保する
309:   for idx := FCount downto index + 1 do
310:   begin
311:     FKeys[idx] := FKeys[idx - 1];
312:     FVals[idx] := FVals[idx - 1];
313:   end;
314: 
315:   FKeys[index] := new_key;
316:   FVals[index] := new_val;
317: 
318:   Inc(FCount);
319: end;
320: 
321: procedure TBTreeNode.SetVals(Index: Integer; const Value: Integer);
322: begin
323:   FVals[Index] := Value;
324: end;
325: 
326: { TBtree }
327: 
328: procedure TBtree.Add(new_key, new_val: Integer);
329: var
330:   created_node, old_root : TBTreeNode;
331:   return_key, return_val : Integer;
332: begin
333:   //ルートに対して新しいキーを追加した結果、ルートが分割されるかどうかで処理を分ける
334:   if(FRoot.InternalAdd(new_key, new_val, created_node, return_key, return_val)=True) then
335:   begin
336:     old_root := FRoot;
337:     FRoot := TBTreeNode.Create(FOrder);
338:     FRoot.Keys[0] := return_key;
339:     FRoot.Vals[0] := return_val;
340:     FRoot.ChildNodes[0] := old_root;
341:     FRoot.ChildNodes[1] := created_node;
342:     FRoot.SetCount(1);
343:   end;
344: end;
345: 
346: //B木のコンストラクタ
347: constructor TBtree.Create(Order: Integer);
348: begin
349:   inherited Create;
350: 
351:   FOrder := Order;
352:   FRoot  := TBtreeNode.Create(Order);
353: end;
354: 
355: //B木のデストラクタ
356: destructor TBtree.Destroy;
357: begin
358:   FRoot.Free;
359: 
360:   inherited;
361: end;
362: 
363: //ツリーの内部状態を返す
364: function TBtree.DumpNodes: String;
365: begin
366:   FRoot.DumpNodes(Result, 0);
367: end;
368: 
369: end.

　今回はB木に対する要素の追加についてみてきました、AVL木と比べると直感的には分かりやすいのではないかと思います。なるべく各節点のオブジェクト自体にロジックを集中しようと思って実装してみましたが、通常はツリーオブジェクト側にこうしたロジックを実装しています。

　なぜかというと、B木の利点として1つのノードが一定の大きさをもったデータ構造となるため、ファイルシステムへの出し入れ（ページングともいいますね）がやりやすいという利点があるので、データを含む節点側にはあまりロジックを実装していません。

　しかし、いずれにせよTObject派生のオブジェクトとして実装しているわけですし、ページングする必要のあるキーやノードの配列については、そこだけをストリームにして書き出したり読み込んだりするということも可能なわけですから、よりオブジェクト指向的な実装をという考えでチャレンジしてみました。

　さて、次回はB木からのデータの削除にチャレンジします。ご期待下さい。

3/3

Index
RDBMSで使われるB木を学ぼう
	Page1 B木とは何か B木の成長
	Page2 B木への要素の追加（葉の場合） B木への要素の追加（葉でない場合） B木の実装の工夫
	Page3 B木のテストプログラム
	Appendix BTree.pasのソースコード

Delphiアルゴリズムトレーニング

　Coding Edgeお勧め記事

	いまさらアルゴリズムを学ぶ意味コーディングに役立つ！アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
	Zope 3の魅力に迫る Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
	貧弱環境プログラミングのススメ柴田淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
	Haskellプログラミングの楽しみ方のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
	ちょっと変わったLisp入門 Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
	more

　　Coding Edgeフォーラム

フィード　 2.0／1.0／0.91

Coding Edge フォーラム新着記事

プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る （2017/7/20）
　C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る
エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね？ （2017/7/13）
　C言語の「Hello World！」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る
VBAにおけるFileDialog操作の基本＆ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 （2017/7/10）
　指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog／エクスプローラー操作の基本を紹介します
さらば残業！　面倒くさいエクセル業務を楽にする「Excel VBA」とは （2017/7/6）
　日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

Coding Edge

注目のテーマ

Coding Edge 記事ランキング

本日月間

＠IT

第5回 RDBMSで使われるB木を学ぼう

B木のテストプログラム

注目のテーマ

Coding Edge 記事ランキング

転職／派遣情報を探す

年収６００万円！エンジニア向けの求人満載。転職希望者必見

エンジニアの転職なら【転職サーチ】