def check
      branch_depth = nil

      traverse do |node, position, stack|
        if position == 0
          if node.parent
            # After a split the nodes will only have half the maximum keys.
            # For branch nodes one of the split nodes will have even 1 key
            # less as this will become the branch key in a parent node.
            if node.keys.size < min_keys - (node.is_leaf? ? 0 : 1)
              node.error "BigTree node #{node._id} has too few keys"
              return false
            end
          end

          if node.keys.size > @tree.node_size
            node.error "BigTree node must not have more then " +
              "#{@tree.node_size} keys, but has #{node.keys.size} keys"
            return false
          end

          last_key = nil
          node.keys.each do |key|
            if last_key && key < last_key
              node.error "Keys are not increasing monotoneously: " +
                "#{node.keys.inspect}"
              return false
            end
            last_key = key
          end

          if node.is_leaf?
            if branch_depth
              unless branch_depth == stack.size
                node.error "All leaf nodes must have same distance from root"
                return false
              end
            else
              branch_depth = stack.size
            end
            if node.prev_sibling.nil?
              if @tree.first_leaf != node
                node.error "Leaf node #{node._id} has no previous sibling " +
                  "but is not the first leaf of the tree"
                return false
              end
            elsif node.prev_sibling.next_sibling != node
              node.error "next_sibling of previous sibling does not point to " +
                "this node"
              return false
            end
            if node.next_sibling.nil?
              if @tree.last_leaf != node
                node.error "Leaf node #{node._id} has no next sibling " +
                  "but is not the last leaf of the tree"
                return false
              end
            elsif node.next_sibling.prev_sibling != node
              node.error "previous_sibling of next sibling does not point to " +
                "this node"
              return false
            end
            unless node.keys.size == node.values.size
              node.error "Key count (#{node.keys.size}) and value " +
                "count (#{node.values.size}) don't match"
                return false
            end
            if node.children
              node.error "children must be nil for a leaf node"
              return false
            end
          else
            if node.values
              node.error "values must be nil for a branch node"
              return false
            end
            unless node.children.size == node.keys.size + 1
              node.error "Key count (#{node.keys.size}) must be one " +
                "less than children count (#{node.children.size})"
                return false
            end
            node.children.each_with_index do |child, i|
              unless child.is_a?(BigTreeNode)
                node.error "Child #{i} is of class #{child.class} " +
                  "instead of BigTreeNode"
                return false
              end
              unless child.parent.is_a?(BigTreeNode)
                node.error "Parent reference of child #{i} is of class " +
                  "#{child.class} instead of BigTreeNode"
                return false
              end
              if child == node
                node.error "Child #{i} point to self"
                return false
              end
              if stack.include?(child)
                node.error "Child #{i} points to ancester node"
                return false
              end
              unless child.parent == node
                node.error "Child #{i} does not have parent pointing " +
                  "to this node"
                return false
              end
              if i > 0
                unless node.children[i - 1].next_sibling == child
                  node.error "next_sibling of node " +
                    "#{node.children[i - 1]._id} " +
                    "must point to node #{child._id}"
                  return false
                end
              end
              if i < node.children.length - 1
                unless child == node.children[i + 1].prev_sibling
                  node.error "prev_sibling of node " +
                    "#{node.children[i + 1]._id} " +
                    "must point to node #{child._id}"
                  return false
                end
              end
            end
          end
        elsif position <= node.keys.size
          # These checks are done after we have completed the respective child
          # node with index 'position - 1'.
          index = position - 1
          if node.is_leaf?
            if block_given?
              # If a block was given, call this block with the key and value.
              return false unless yield(node.keys[index], node.values[index])
            end
          else
            unless node.children[index].keys.last < node.keys[index]
              node.error "Child #{node.children[index]._id} " +
                "has too large key #{node.children[index].keys.last}. " +
                "Must be smaller than #{node.keys[index]}."
              return false
            end
            unless node.children[position].keys.first >= node.keys[index]
              node.error "Child #{node.children[position]._id} " +
                "has too small key #{node.children[position].keys.first}. " +
                "Must be larger than or equal to #{node.keys[index]}."
              return false
            end
          end
        end
      end

      true
    end
def check
      branch_depth = nil

      traverse do |node, position, stack|
        if position == 0
          if node.parent
            # After a split the nodes will only have half the maximum keys.
            # For branch nodes one of the split nodes will have even 1 key
            # less as this will become the branch key in a parent node.
            if node.keys.size < min_keys - (node.is_leaf? ? 0 : 1)
              node.error "BigTree node #{node._id} has too few keys"
              return false
            end
          end

          if node.keys.size > @tree.node_size
            node.error "BigTree node must not have more then " +
              "#{@tree.node_size} keys, but has #{node.keys.size} keys"
            return false
          end

          last_key = nil
          node.keys.each do |key|
            if last_key && key < last_key
              node.error "Keys are not increasing monotoneously: " +
                "#{node.keys.inspect}"
              return false
            end
            last_key = key
          end

          if node.is_leaf?
            if branch_depth
              unless branch_depth == stack.size
                node.error "All leaf nodes must have same distance from root"
                return false
              end
            else
              branch_depth = stack.size
            end
            if node.prev_sibling.nil?
              if @tree.first_leaf != node
                node.error "Leaf node #{node._id} has no previous sibling " +
                  "but is not the first leaf of the tree"
                return false
              end
            elsif node.prev_sibling.next_sibling != node
              node.error "next_sibling of previous sibling does not point to " +
                "this node"
              return false
            end
            if node.next_sibling.nil?
              if @tree.last_leaf != node
                node.error "Leaf node #{node._id} has no next sibling " +
                  "but is not the last leaf of the tree"
                return false
              end
            elsif node.next_sibling.prev_sibling != node
              node.error "previous_sibling of next sibling does not point to " +
                "this node"
              return false
            end
            unless node.keys.size == node.values.size
              node.error "Key count (#{node.keys.size}) and value " +
                "count (#{node.values.size}) don't match"
                return false
            end
            if node.children
              node.error "children must be nil for a leaf node"
              return false
            end
          else
            if node.values
              node.error "values must be nil for a branch node"
              return false
            end
            unless node.children.size == node.keys.size + 1
              node.error "Key count (#{node.keys.size}) must be one " +
                "less than children count (#{node.children.size})"
                return false
            end
            node.children.each_with_index do |child, i|
              unless child.is_a?(BigTreeNode)
                node.error "Child #{i} is of class #{child.class} " +
                  "instead of BigTreeNode"
                return false
              end
              unless child.parent.is_a?(BigTreeNode)
                node.error "Parent reference of child #{i} is of class " +
                  "#{child.class} instead of BigTreeNode"
                return false
              end
              if child == node
                node.error "Child #{i} point to self"
                return false
              end
              if stack.include?(child)
                node.error "Child #{i} points to ancester node"
                return false
              end
              unless child.parent == node
                node.error "Child #{i} does not have parent pointing " +
                  "to this node"
                return false
              end
              if i > 0
                unless node.children[i - 1].next_sibling == child
                  node.error "next_sibling of node " +
                    "#{node.children[i - 1]._id} " +
                    "must point to node #{child._id}"
                  return false
                end
              end
              if i < node.children.length - 1
                unless child == node.children[i + 1].prev_sibling
                  node.error "prev_sibling of node " +
                    "#{node.children[i + 1]._id} " +
                    "must point to node #{child._id}"
                  return false
                end
              end
            end
          end
        elsif position <= node.keys.size
          # These checks are done after we have completed the respective child
          # node with index 'position - 1'.
          index = position - 1
          if node.is_leaf?
            if block_given?
              # If a block was given, call this block with the key and value.
              return false unless yield(node.keys[index], node.values[index])
            end
          else
            unless node.children[index].keys.last < node.keys[index]
              node.error "Child #{node.children[index]._id} " +
                "has too large key #{node.children[index].keys.last}. " +
                "Must be smaller than #{node.keys[index]}."
              return false
            end
            unless node.children[position].keys.first >= node.keys[index]
              node.error "Child #{node.children[position]._id} " +
                "has too small key #{node.children[position].keys.first}. " +
                "Must be larger than or equal to #{node.keys[index]}."
              return false
            end
          end
        end
      end

      true
    end
Check consistency of the node and all subsequent nodes. In case an error
 is found, a message is logged and false is returned.
 @yield [key, value]
 @return [Boolean] true if tree has no errors