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
 11  attr_writer :parent
 12
 13  def position(k)
 14    i = 0
 15    @keys.each do |key|
 16      break if(k < key)
 17      i = i + 1
 18    end
 19    i
 20  end
 21
 22  def balance
 23    len = @keys.length
 24    if(len > @slot)
 25      prepare_balance
 26      m = len / 2
 27      ck = @keys[m]
 28      left, right = split(m)
 29      @parent.balance_parent(ck, left, right, self)
 30    end
 31  end
 32
 33  def prepare_balance
 34    unless @parent
 35      @parent = Node.new(@slot, [], nil, [])
 36      @@root = @parent
 37    end
 38  end
 39
 40  def log
 41    len = @keys.length
 42    p "len: #{len}"
 43    p "keys: " + @keys.to_s
 44    p "@slot: #{@slot}"
 45    m = len / 2
 46    p "m: " + m.to_s
 47    mk = @keys[m]
 48    p "mk: " + mk.to_s
 49  end
 50end
 51
 52class Node < AbstractNode
 53  def Node.root
 54    @@root
 55  end
 56
 57  def initialize(n, keys, parent, children)
 58    super(n, keys, parent)
 59    @children = children
 60    @children.each do |c|
 61      c.parent = self
 62    end
 63  end
 64
 65  def search(k)
 66    i = 0
 67    @keys.each do |key|
 68      break if(k <= key)
 69      i += 1
 70    end
 71    return nil unless @children[i]
 72    @children[i].search(k)
 73  end
 74
 75  def insert(k, v)
 76    pos = position(k)
 77    c = @children[pos]
 78    c.insert(k, v)
 79  end
 80
 81  def split(m)
 82    left = Node.new(@slot, @keys[0..m-1], @parent, @children[0..m])
 83    right = Node.new(@slot, @keys[m+1..@keys.length-1],
 84                     @parent, @children[m+1, @children.length-1])
 85    return left, right
 86  end
 87
 88  def balance_parent(k, left, right, child)
 89    pos = position(k)
 90    @keys.insert(pos, k)
 91    merge_children(pos, left, right)
 92    @children.delete(child)
 93    balance
 94  end
 95
 96  def merge_children(pos, left, right)
 97    @children.insert(pos, left);
 98    @children.insert(pos + 1, right)
 99  end
100
101  def dump(indent)
102    puts indent + "Node: #{@keys.to_s} self: #{self} @parent=#{@parent}"
103    @children.each do |c|
104      c.dump("  " << indent) if c
105    end
106  end
107end
108
109class Leaf < AbstractNode
110  def initialize(n, keys, values, parent)
111    super(n, keys, parent)
112    @values = values
113  end
114
115  def insert(k, v)
116    pos = position(k)
117    @keys.insert(pos, k)
118    @values.insert(pos, v)
119    balance
120  end
121
122  def search(k)
123    i = 0
124    @keys.each do |key|
125      return @values[i] if(k == key)
126      break if(k < key)
127      i += 1
128    end
129    nil
130  end
131
132  def split(m)
133    left = Leaf.new(@slot, @keys[0..m], @values[0..m], @parent)
134    right = Leaf.new(@slot, @keys[m+1..@keys.length-1],
135                     @values[m+1..@values.length-1], @parent)
136    return left, right
137  end
138
139  def dump(indent)
140    puts indent + "Leaf: keys: #{@keys.to_s} values: #{@values.to_s} @parent=#{@parent}"
141  end
142end

main.rb:

 1require 'b_plus_tree'
 2
 3l = Leaf.new(4, [], [], nil)
 4(1..90).each do |i|
 5  Node.root.insert(i, 90-i+1)
 6  Node.root.dump("")
 7  puts
 8end
 9
10puts "Node.root.search(27): #{Node.root.search(27)}"
11puts "Node.root.search(90): #{Node.root.search(90)}"
12puts "Node.root.search(91): #{Node.root.search(91)}"

この実装では、各ノードのデータをファイルには書いていません。また、ノードの削除がありません。

ノード情報をファイルへ永続化することを考えると、内部ノードか葉ノードかの区別はクラスで分けるよりもフラグで持っていた方が良いのですが、後から見て分かりやすい形にしておきたかったので、内部ノード(Node)と葉ノード(Leaf)は分けてみました。

いくつかB+Treeについて説明しているページを読んだものの、実装は何も考えずにイチから書いたので、冗長な箇所があると思います。他のRuby実装と比較してみようかと。