B+ シーケンス木の検証コード

B+ シーケンス木の検証に使ってきた check? メソッドを整理して置いておきます。 このメソッドは、 木が B+ 木の条件を満たしているか、 さらに、 シーケンス木としての条件を満たしているかをチェックします。 検証は深さ優先で進めます。

# in rspec file:
#
#     @sq = BplusSequence.new
#     #do something
#     expect(@sq).to be_check
#
class BplusSequence
  class CheckContext
    attr_accessor :first_occurence_depth
    attr_accessor :tree_array
    attr_accessor :dlist_array
  end

  def check?
    env = CheckContext.new
    env.first_occurence_depth = nil
    env.tree_array = []
    env.dlist_array = []
    kont = [[@root, 1]]
    while not kont.empty?
      page, depth = kont.shift
      check_page_class?(page, depth, env, kont) or return false
      check_page_size?(page, depth, env, kont) or return false
      if page.leaf?
        check_leaf?(page, depth, env, kont) or return false
      else
        check_node?(page, depth, env, kont) or return false
        # 深さ優先
        page.cell.reverse_each {|cell| kont.unshift([cell.value, depth + 1]) }
      end
    end
    check_leaf_link?(page, depth, env, kont)
  end

#@<check_page_class? 述語@>
#@<check_page_size? 述語@>
#@<check_node? 述語@>
#@<check_leaf? 述語@>
#@<check_leaf_link? 述語@>
end

最初に page が Page オブジェクトか、 page.cell の全要素が Cell オブジェクトかどうかを検証します。

#@<check_page_class? 述語@>=
  def check_page_class?(page, depth, env, kont)
    Page === page or raise ArgumentError, "not Page:#{page.class}"
    page.cell.all? {|cell| Cell === cell }
  end

B+ 木の条件をページ・サイズが満たしていることを検証します。 B+ 木では、 すべてのページで子の数は ORDER 以下でなければなりません。 さらに、 根ではない他のすべてのページの (B+ 木のキーに相当する) 子に挟まれている要素数注釈の数は HALF_SIZE 以上でなければなりません。 子に挟まれているという制約により最後のセルの要素数注釈を勘定に入れず、 それを除いたセル数で比較します。

  def check_page_size?(page, depth, env, kont)
    if @root.equal?(page)
      page.size <= ORDER
    else
      HALF_SIZE <= page.size - 1 and page.size <= ORDER
    end
  end

葉でないページを検証します。 先頭セルの count は、 先頭セルの value が参照するページの末尾 count に一致しなければなりません。 それ以外のセルの count は、 そのセルの value が参照するページの末尾 count に、 一つ前のセルの count を足したものに一致しなければなりません。 念を入れて、 全セルの value がすべて葉を参照しているか、 葉でないページを参照しているかのいずれかであることを検証しておきます。

  def check_node?(page, depth, env, kont)
    page[0].value.count == page[0].count or return false
    (1 ... page.size).all? {|i|
      page[i - 1].count + page[i].value.count == page[i].count
    } or return false
    if page.cell[0].value.leaf?
      page.cell.all? {|cell| cell.value.leaf? }
    else
      page.cell.all? {|cell| not cell.value.leaf? }
    end
  end

葉であるページを検証します。 まず、 根から葉までの深さが、 すべての葉で同一であることを検証します。 続いて、 先頭セルの count が 1 で、 それに続くセルの count が増加値 1 の等差数列になっていることを検証します。 さらに、 葉のリストの順番が一致するかどうかを後で調べるために、 葉の要素を tree_array に追加しておきます。

  def check_leaf?(page, depth, env, kont)
    env.first_occurence_depth ||= depth
    env.first_occurence_depth == depth or return false
    if not page.empty?
      1 == page[0].count or return false
      (1 ... page.size).all? {|i|
        page[i - 1].count + 1 == page[i].count
      } or return false
      page.cell.each {|cell| env.tree_array << cell.value }
    end
    true
  end

木構造の検証に続いて、 葉のリストを検証します。 全部の葉が両端 nil 終端の双方向リンクの条件を満たしていることを検証します。 さらに、 last インスタンス変数を末尾の葉に束縛していることを検証します。 同時に、 葉の要素を dlist_array に追加していきます。 リンクを終わりまで辿ってから、 木で要素を順に集めておいた tree_array と dlist_array が一致することを検証します。

  def check_leaf_link?(page, depth, env, kont)
    page = @first
    while not page.nil?
      (page.back.nil? or page.back.forw.equal?(page)) or return false
      (page.forw.nil? or page.forw.back.equal?(page)) or return false
      (not page.forw.nil? or page.equal?(@last)) or return false
      page.cell.each {|cell| env.dlist_array << cell.value }
      page = page.forw
    end
    env.tree_array == env.dlist_array
  end