B+Tree

b_plus_tree.rb

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

main.rb

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)}"