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

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

はやしつとむ
アナハイムテクノロジー株式会社

2009/6/22

icon B木のテストプログラム

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

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

葉のバケットにキーを追加1
●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木からのデータの削除にチャレンジします。ご期待下さい。

prev
3/3
 

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

index 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の世界を体験してみよう
  Coding Edgeフォーラムフィード  2.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間