Skip to content

Instantly share code, notes, and snippets.

@evenchange4
Forked from masayuki038/b_plus_tree.rb
Created October 9, 2012 14:27
Show Gist options
  • Save evenchange4/3859163 to your computer and use it in GitHub Desktop.
Save evenchange4/3859163 to your computer and use it in GitHub Desktop.
B+Tree
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
#log
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
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)}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment