act-act about projects rss

B+Tree in Ruby

B+Tree And Ruby

以前、java.util.MapをBSONでファイルに保存するFileStoredMapというコレクションクラスを書きました。

今度はそれのTree版を書こうと考えたのですが、Tree自体をこれまでロクに書いたことが無かったので、まずはRubyでB+Treeを書いてみました。こういった作って動かしてみてどういうものか確認するのは、スクリプト言語の方が楽なので。実際、動かしながら作っていくのはなかなか面白い作業でした。

b_plus_tree.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
class AbstractNode
  @@root = nil

  def initialize(n, keys, parent)
    @slot = n
    @keys = keys
    @parent = parent
    @@root = self unless @@root
  end

  attr_writer :parent

  def position(k)
    i = 0
    @keys.each do |key|
      break if(k < key)
      i = i + 1
    end
    i
  end

  def balance
    len = @keys.length
    if(len > @slot)
      prepare_balance
      m = len / 2
      ck = @keys[m]
      left, right = split(m)
      @parent.balance_parent(ck, left, right, self)
    end
  end

  def prepare_balance
    unless @parent
      @parent = Node.new(@slot, [], nil, [])
      @@root = @parent
    end
  end

  def log
    len = @keys.length
    p "len: #{len}"
    p "keys: " + @keys.to_s
    p "@slot: #{@slot}"
    m = len / 2
    p "m: " + m.to_s
    mk = @keys[m]
    p "mk: " + mk.to_s
  end
end

class Node < AbstractNode
  def Node.root
    @@root
  end

  def initialize(n, keys, parent, children)
    super(n, keys, parent)
    @children = children
    @children.each do |c|
      c.parent = self
    end
  end

  def search(k)
    i = 0
    @keys.each do |key|
      break if(k <= key)
      i += 1
    end
    return nil unless @children[i]
    @children[i].search(k)
  end

  def insert(k, v)
    pos = position(k)
    c = @children[pos]
    c.insert(k, v)
  end

  def split(m)
    left = Node.new(@slot, @keys[0..m-1], @parent, @children[0..m])
    right = Node.new(@slot, @keys[m+1..@keys.length-1],
                     @parent, @children[m+1, @children.length-1])
    return left, right
  end

  def balance_parent(k, left, right, child)
    pos = position(k)
    @keys.insert(pos, k)
    merge_children(pos, left, right)
    @children.delete(child)
    balance
  end

  def merge_children(pos, left, right)
    @children.insert(pos, left);
    @children.insert(pos + 1, right)
  end

  def dump(indent)
    puts indent + "Node: #{@keys.to_s} self: #{self} @parent=#{@parent}"
    @children.each do |c|
      c.dump("  " << indent) if c
    end
  end
end

class Leaf < AbstractNode
  def initialize(n, keys, values, parent)
    super(n, keys, parent)
    @values = values
  end

  def insert(k, v)
    pos = position(k)
    @keys.insert(pos, k)
    @values.insert(pos, v)
    balance
  end

  def search(k)
    i = 0
    @keys.each do |key|
      return @values[i] if(k == key)
      break if(k < key)
      i += 1
    end
    nil
  end

  def split(m)
    left = Leaf.new(@slot, @keys[0..m], @values[0..m], @parent)
    right = Leaf.new(@slot, @keys[m+1..@keys.length-1],
                     @values[m+1..@values.length-1], @parent)
    return left, right
  end

  def dump(indent)
    puts indent + "Leaf: keys: #{@keys.to_s} values: #{@values.to_s} @parent=#{@parent}"
  end
end

main.rb

1
2
3
4
5
6
7
8
9
10
11
12
require 'b_plus_tree'

l = Leaf.new(4, [], [], nil)
(1..90).each do |i|
  Node.root.insert(i, 90-i+1)
  Node.root.dump("")
  puts
end

puts "Node.root.search(27): #{Node.root.search(27)}"
puts "Node.root.search(90): #{Node.root.search(90)}"
puts "Node.root.search(91): #{Node.root.search(91)}"

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

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

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