jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a...@apache.org
Subject [35/65] [abbrv] jena git commit: JENA-1397: Rename java packages
Date Tue, 03 Oct 2017 19:34:21 GMT
http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNode.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNode.java b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNode.java
new file mode 100644
index 0000000..a9a9fa5
--- /dev/null
+++ b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNode.java
@@ -0,0 +1,1508 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.dboe.trans.bplustree;
+
+import static org.apache.jena.dboe.base.record.Record.keyGT;
+import static org.apache.jena.dboe.base.record.Record.keyLT;
+import static org.apache.jena.dboe.base.record.Record.keyNE;
+import static org.apache.jena.dboe.trans.bplustree.BPT.*;
+
+import java.util.ArrayList ;
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.apache.jena.atlas.io.IndentedLineBuffer ;
+import org.apache.jena.atlas.io.IndentedWriter ;
+import org.apache.jena.dboe.base.block.Block;
+import org.apache.jena.dboe.base.block.BlockMgr;
+import org.apache.jena.dboe.base.buffer.PtrBuffer;
+import org.apache.jena.dboe.base.buffer.RecordBuffer;
+import org.apache.jena.dboe.base.page.PageBlockMgr;
+import org.apache.jena.dboe.base.record.Record;
+import org.apache.jena.dboe.sys.SystemIndex;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+
+public final class BPTreeNode extends BPTreePage
+{
+    private static Logger log = LoggerFactory.getLogger(BPTreeNode.class) ;
+    @Override protected Logger getLogger() { return log ; }
+   
+    /*package*/ Block block ;
+    /** Page id.
+     *  Pages are addressed by ints (a page ref does in on-disk blocks)
+     *  although blocks are addressed in longs.
+     *  1k pages => 2Tbyte file limit.
+     */
+    /*package*/int id ;             // Or block.getId()            
+    
+    private int parent ;
+    private int count ;             // Number of records.  Number of pointers is +1
+    
+    // "Leaf" of the BPTree is the lowest level of ptr/key splits, not the data blocks.
+    // We need to know this to know which block manager the block pointers refer to.
+    private boolean isLeaf ;        
+
+    private RecordBuffer records ;
+    /*package*/ void setRecordBuffer(RecordBuffer r) { records = r ; }
+    
+    // Accessed by BPlusTreeFactory
+    /*package*/ PtrBuffer ptrs ;
+    /*package*/ void setPtrBuffer(PtrBuffer pb) { ptrs = pb ; }
+
+    /* B+Tree
+     * 
+     * Two block managers : 
+     *   one for Nodes (BPlusTreePages => BPlusTreeNode)
+     *   one for Leaves (RecordBufferPages)
+     * The split key is the held in the highest in the block  
+     * 
+     * A "leaf" node is a leaf of the B+Tree part, and points to 
+     * highest record in a RecordBuffer 
+     *
+     * Example for N = 2
+     *  2*N:      MaxRec = 4, MaxPtr = 5,
+     *  Max-1:    HighRec = 3, HighPtr = 4
+     *  N-1:      MinRec = 1, MinPtr = 2
+     *  
+     * which is why a tree of order <2 does not make sense. 
+     *  
+     *
+     * BPTreeNode:
+     * 
+     *      +------------------------+
+     *      |-| K0 | K1 | K2 | K3 |--|
+     *      +------------------------+
+     *      | P0 | P1 | P2 | P3 | P4 |
+     *      +------------------------+
+     *
+     *      +------------------------+
+     *      | | K0 | K1 | ** | ** |--|
+     *      +------------------------+
+     *      | P0 | P1 | P2 | ** | ** |
+     *      +------------------------+
+     *      
+     * BPTreeRecords -> RecordBuffer:
+     *      
+     *      +------------------------+
+     *      | K0 | K1 | K2 | ** | ** |
+     *      +------------------------+
+     *      
+     * The size of records blocks and size of tree nodes don't have to be the same.
+     * They use different page managers, and are in different files.  
+     *
+     * The minimal tree is one, leaf, root BPTreeNode and one BPTreeRecords page.
+     * 
+     * Pictures:      
+     *      /--\ \--\
+     * means a block with free space introduced between records[i] and records[i+1], ptrs[i+1]/ptrs[i+2]
+     * Lower half is a valid structure (except for overall size) 
+     *       
+     *      /--/ /--\
+     * means a block with free space introduced between records[i] and records[i+1], ptrs[i]/ptrs[i+1]
+     * Upper half is a valid structure (except for overall size) 
+     */
+
+    // Branch nodes only need create branch nodes (splitting sideways)
+    // Leaf nodes only create leaf nodes.
+    // The root is an exception.
+    
+    private BPTreeNode create(int parent, boolean isLeaf) {
+        return create(bpTree, parent, isLeaf) ;
+    }
+
+    private static BPTreeNode create(BPlusTree bpTree, int parent, boolean isLeaf) {
+        BPTreeNode n = bpTree.getNodeManager().createNode(parent) ;
+        n.isLeaf = isLeaf ;
+        return n ;
+    }
+
+    /*package*/ BPTreeNode(BPlusTree bpTree) {
+        super(bpTree) ;
+        // Other set by BPTreeNodeMgr.formatBPTreeNode 
+    }
+    
+    // ---- [[TXN]] ** work for transactions.
+    void checkTxn() {}
+    void checkWriteTxn() {}
+
+//    static BPTreeNode xensureModifiableRoot(BPTreeNode root, Object state) {
+//        BPTreeNode root2 = promote1(root, root, NO_ID)(null, root) ;
+//        if ( root != root2 && root.getId() != root2.getId() ) {
+//            System.err.println("Cloned root") ;
+//            if ( state == null )
+//                System.err.println("... no state") ;
+//            // [[TXN]] ** Root clone
+//            // get state and update root.
+//        }
+//        return root2 ;
+//    }
+
+    // ----
+    
+    @Override
+    public void reset(Block block) {
+        this.block = block ;
+        // reformat block (sets record and pointer buffers)
+        BPTreeNodeMgr.formatBPTreeNode(this, bpTree, block, isLeaf, parent, count) ;
+    }
+    
+    /** Get the page at slot idx - switch between B+Tree and records files */
+    /*package*/ BPTreePage get(int idx) {
+        if ( false && logging(log) ) {
+            String leafOrNode = isLeaf ? "L" : "N" ;
+            log(log, "%d[%s].get(%d)", id, leafOrNode, idx) ; 
+        }
+        int subId = ptrs.get(idx) ;
+        PageBlockMgr<? extends BPTreePage> pbm = getPageBlockMgr() ;
+        // Always get a "read" block - it must be promoted to a "write" block
+        // to update it.  Getting a write block is unhelpful as many blocks
+        // during a write operation are only read.
+        return pbm.getRead(subId, this.getId()) ;
+    }
+
+    private PageBlockMgr<? extends BPTreePage> getPageBlockMgr() {
+        if ( isLeaf )
+            return bpTree.getRecordsMgr() ;
+        else
+            return bpTree.getNodeManager() ;
+    }
+    
+    // ---------- Public calls.
+    // None of these are called recursively.
+
+    /** Find a record, using the active comparator */
+    public static Record search(BPTreeNode root, Record rec) {
+        root.internalCheckNodeDeep() ;
+        if ( ! root.isRoot() )
+            throw new BPTreeException("Search not starting from the root: " + root) ;
+        AccessPath path = new AccessPath(root) ;
+        Record r = root.internalSearch(path, rec) ;
+        return r ;
+    }
+
+    /** Insert a record - return existing value if any, else null */
+    public static Record insert(BPTreeNode root, Record record) {
+        if ( logging(log) ) {
+            log(log, "** insert(%s) / root=%d", record, root.getId()) ;
+            if ( DumpTree )
+                root.dump() ;
+        }
+
+        if ( !root.isRoot() )
+            throw new BPTreeException("Insert begins but this is not the root") ;
+        
+        if ( root.isFull() ) {
+            // Root full - root split is a special case.
+            splitRoot(root) ;
+            if ( DumpTree )
+                root.dump() ;
+        }
+
+        AccessPath path = new AccessPath(root) ;
+        // Root ready - call insert proper.
+        Record result = root.internalInsert(path, record) ;
+
+        root.internalCheckNodeDeep() ;
+
+        if ( logging(log) ) {
+            log(log, "** insert(%s) / finish", record) ;
+            if ( DumpTree )
+                root.dump() ;
+        }
+        return result ;
+    }
+
+    /** Delete a record - return the old value if there was one, else null */
+    public static Record delete(BPTreeNode root, Record rec) {
+        if ( logging(log) ) {
+            log(log, "** delete(%s) / start", rec) ;
+            if ( BPT.DumpTree )
+                root.dump() ;
+        }
+        if ( !root.isRoot() )
+            throw new BPTreeException("Delete begins but this is not the root") ;
+
+        AccessPath path = new AccessPath(root) ;
+        
+        if ( root.isLeaf && root.count == 0 ) {
+            // Special case. Just a records block. Allow that to go too small.
+            BPTreePage page = root.get(0) ;
+            if ( BPT.CheckingNode && !(page instanceof BPTreeRecords) )
+                BPT.error("Zero size leaf root but not pointing to a records block") ;
+            trackPath(path, root, 0, page) ;
+            Record r = page.internalDelete(path, rec) ;
+            page.release() ;
+            if ( r != null )
+                root.write() ;
+            if ( BPT.DumpTree )
+                root.dump() ;
+            return r ;
+        }
+
+        // Entry: checkNodeDeep() ;
+        Record v = root.internalDelete(path, rec) ;
+        // Fix the root in case it became empty in deletion process.
+        if ( !root.isLeaf && root.count == 0 ) {
+            reduceRoot(root) ;
+            root.bpTree.newRoot(root) ;
+            root.internalCheckNodeDeep() ;
+        }
+
+        if ( logging(log) ) {
+            log(log, "** delete(%s) / finish", rec) ;
+            if ( BPT.DumpTree )
+                root.dump() ;
+        }
+        return v ;
+    }
+
+    /** Iterator over the pages below that have records between minRec (inclusive) and maxRec(exclusive).
+     *  There may be other records as as well.
+     * @param minRec
+     * @param maxRec
+     * @return Iterator&lt;BPTreePage>
+     */
+    Iterator<BPTreePage> iterator(Record minRec, Record maxRec) {
+        if ( minRec != null && maxRec != null && Record.keyGE(minRec, maxRec) )
+            return null ;//throw new IllegalArgumentException("minRec >= maxRec: "+minRec+" >= "+maxRec ) ;
+        
+        int x1 = 0 ;
+        if ( minRec != null ) {
+            x1 = findSlot(minRec) ;
+            // If there is an exact match, we still need to go down that place to get the max.
+            // If there is no match, it returns -(i+1) and we need to go down the tree at i.
+            // Same effect - start at x1
+            // TODO Optimization - get max record on min side once and for all if exact match.
+            x1 = apply(x1) ;
+        }
+        
+        int x2 = this.getCount() ;    // Highest place to look. Inclusive.   
+        if ( maxRec != null ) {
+            // If there is an exact match, we need to go down that place to get the record upto max.
+            // If there is no match, it returns -(i+1) and we need to go down the tree at i to get from last key to max (exclusive).
+            // Same effect - start at x2 inclusive.
+            x2 = findSlot(maxRec) ;
+            x2 = apply(x2) ;
+        }
+        // Pages from pointer slots x1 to x2 (inc because while we exclude maxRec, 
+        // keys are only a max of the subtree they mark out.
+        
+        // XXX Just grab them now - later, keep indexes and fetch on next(). 
+        // XXX Epoch tracking 
+        
+        List<BPTreePage> x = new ArrayList<>(x2-x1+1) ;
+        for ( int i = x1 ; i <= x2 ; i++ )
+            x.add(get(i)) ;
+        
+        return x.iterator() ;
+    }
+    
+//    // OUT OF DATE WITH MVCC
+//    /**
+//     * Returns the id of the records buffer page for this record. Records Buffer
+//     * Page NOT read; record may not exist
+//     */
+//    static int recordsPageId(BPTreeNode node, Record fromRec) {
+//        // Used by BPlusTree.iterator
+//        // Walk down the B+tree part of the structure ...
+//        while (!node.isLeaf) {
+//            BPTreePage page = (fromRec == null) ? node.get(0) : node.findHere(null, fromRec) ;
+//            // Not a leaf so we can cast safely.
+//            BPTreeNode n = (BPTreeNode)page ;
+//            // Release if not root.
+//            if ( !node.isRoot() )
+//                node.release() ;
+//            node = n ;
+//        }
+//        // ... then find the id of the next step down, 
+//        // but do not touch the records buffer page.
+//        int id ;
+//        if ( fromRec == null ) {
+//            // Just get the lowest starting place.
+//            id = node.getPtrBuffer().getLow() ;
+//        } else {
+//            // Get the right id based on starting record.
+//            int idx = node.findSlot(fromRec) ;
+//            idx = apply(idx) ;
+//            id = node.getPtrBuffer().get(idx) ;
+//        }
+//        if ( !node.isRoot() )
+//            node.release() ;
+//        return id ;
+//    }
+
+    final static Record minRecord(BPTreeNode root) {
+        AccessPath path = new AccessPath(root) ; 
+        return root.internalMinRecord(path) ;
+    }
+
+    final static Record maxRecord(BPTreeNode root) {
+        AccessPath path = new AccessPath(root) ; 
+        return root.internalMaxRecord(path) ;
+    }
+    
+    @Override
+    protected Record internalMaxRecord(AccessPath path) {
+        BPTreePage page = get(count) ;
+        trackPath(path, this, count, page) ;
+        Record r = page.internalMaxRecord(path) ;
+        page.release() ;
+        return r ;
+    }
+
+    @Override
+    protected Record internalMinRecord(AccessPath path) {
+        BPTreePage page = get(0) ;
+        trackPath(path, this, 0, page) ;
+        Record r = page.internalMinRecord(path) ;
+        page.release() ;
+        return r ;
+    }
+
+    @Override
+    final Record getLowRecord() {
+        return records.getLow() ;
+    }
+
+    @Override
+    final Record getHighRecord() {
+        return records.getHigh() ;
+    }
+
+    // count is the number of pointers.
+    
+    @Override
+    public final int getMaxSize()          { return bpTree.getParams().getOrder() ; }
+    
+    @Override
+    public final int getCount()            { return count ; }
+ 
+    @Override
+    public final void setCount(int count)  { this.count = count ; }
+    
+    @Override
+  public Block getBackingBlock()           { return block ; }
+    
+    @Override
+    public BlockMgr getBlockMgr()               { return bpTree.getNodeManager().getBlockMgr() ; }
+    
+    /** Do not use without great care */
+    public final RecordBuffer getRecordBuffer()  { return records ; }
+    /** Do not use without great care */
+    public final PtrBuffer getPtrBuffer()        { return ptrs ; }
+    
+    final void setParent(int parentId)           { this.parent = parentId ; } 
+    public final int getParent()                 { return parent ; }
+
+    
+    public final void setIsLeaf(boolean isLeaf)  { this.isLeaf = isLeaf ; }
+    public final boolean isLeaf()                { return this.isLeaf ; }
+    
+    @Override
+    public final int getId()        { return id ; }
+    
+    @Override
+    public String getRefStr() {
+        return String.format("BPTNode[id=%d]", getBackingBlock().getId()) ;
+    }
+
+    @Override
+    final void write()          { bpTree.getNodeManager().write(this) ; } 
+    
+    final private static void trackPath(AccessPath path, BPTreeNode node, int idx, BPTreePage page) {
+        if ( path != null )
+            path.add(node, idx, page) ;
+    }
+    
+    final private static void resetTrackPath(AccessPath path, BPTreeNode node, int idx, BPTreePage page) {
+        if ( path != null ) {
+            path.reset(node, idx, page) ;
+        }
+    }
+    
+    @Override
+    final boolean promote() {
+        if ( bpTree.getNodeManager().isWritable(this.getId()) )
+            return false ;
+        // This calls reset is needed.
+        //   The id, records buffer and pointer buffers need resetting if the block changed.
+        boolean promoteInPlace = bpTree.state().modifiableNodeBlock(getId()) ;
+        if ( promoteInPlace ) {
+            bpTree.getNodeManager().promoteInPlace(this) ;
+            return false ;
+        } else {
+            Block oldBlock = block ;
+            boolean b = bpTree.getNodeManager().promoteDuplicate(this) ;
+            if ( b ) {
+                bpTree.getNodeManager().getBlockMgr().release(oldBlock);
+            }
+            return b ;
+        }
+    }
+    
+    @Override
+    final void release()        { bpTree.getNodeManager().release(this) ; } 
+
+    @Override
+    final void free()           { bpTree.getNodeManager().free(this) ; } 
+    
+    // ============ SEARCH
+    
+    /* 
+     * Do a (binary) search of the node to find the record.
+     *   Returns: 
+     *     +ve or 0 => the index of the record 
+     *     -ve => The insertion point : the immediate higher record or length as (-i-1)
+     *  Convert to +ve and decend to find the RecordBuffer with the record in it. 
+     */
+    
+    @Override
+    final Record internalSearch(AccessPath path, Record rec) {
+        if ( BPT.CheckingNode )
+            internalCheckNode() ;
+        BPTreePage page = findHere(path, rec) ;
+        Record r = page.internalSearch(path, rec) ;
+        page.release() ;
+        return r ;
+    }
+
+    /** Find the next page to look at as we walk down the tree */
+    private final BPTreePage findHere(AccessPath path, Record rec) {
+        int idx = findSlot(rec) ;
+        idx = apply(idx) ;
+        // Find index, or insertion point (immediate higher slot) as (-i-1)
+        // A key is the highest element of the records up to this point
+        // so we search down at slot idx (between something smaller and
+        // something larger).
+        BPTreePage page = get(idx) ;
+        trackPath(path, this, idx, page) ;
+        return page ;
+    }
+    
+    // ============ INSERT
+
+    /*
+     * Traverse this page, ensuring the node below is not full before
+     * decending. Therefore there is always space to do the actual insert.
+     */
+
+    @Override
+    final Record internalInsert(AccessPath path, Record record) {
+        if ( logging(log) )
+            log(log, "internalInsert: %s [%s]", record, this) ;
+
+        internalCheckNode() ;
+
+        int idx = findSlot(record) ;
+        
+
+        if ( logging(log) )
+            log(log, "internalInsert: idx=%d (=>%d)", idx, apply(idx)) ;
+
+        idx = apply(idx) ;
+        BPTreePage page = get(idx) ;
+        trackPath(path, this, idx, page) ;
+
+        if ( logging(log) )
+            log(log, "internalInsert: next: %s", page) ;
+
+        if ( page.isFull() ) {
+            // Need to split the page before descending.
+            split(path, idx, page) ;
+            // Did it shift the insert index?
+            // Examine the record we pulled up in the split.
+            if ( Record.keyGT(record, records.get(idx)) ) {
+                page.release() ;
+                // Yes. Get the new (upper) page
+                idx = idx + 1 ;
+                page = get(idx) ;
+                path.reset(this, idx, page);
+            }
+            internalCheckNode() ;
+        }
+        
+        Record r = page.internalInsert(path, record) ;
+        page.release() ;
+        return r ;
+    }
+
+    /*
+     * Split a non-root node y, held at slot idx in its parent,
+     * which is 'this'and is large enough for a new entry without
+     * another split because we split full blocks on the way down.  
+     * Do this by splitting the node in two (call to BPTree.split)
+     * and inserting the new key/pointer pair.
+     * WRITE(y)
+     * WRITE(z)
+     * WRITE(this)
+     */
+    private void split(AccessPath path, int idx, BPTreePage y) {
+        // logging = true ;
+        if ( logging(log) ) {
+            log(log, "split >> y=%s  this=%s idx=%d", y.getRefStr(), this.getRefStr(), idx) ;
+            log(log, "split --   %s", y) ;
+        }
+
+        internalCheckNode() ;
+        if ( BPT.CheckingNode ) {
+            if ( !y.isFull() )
+                BPT.error("Node is not full") ;
+            if ( this.ptrs.get(idx) != y.getId() ) {
+                int a = this.ptrs.get(idx) ;
+                int b = y.getId() ;
+                BPT.error("Node to be split isn't in right place [%d/%d]", a, b) ;
+            }
+        }
+        internalCheckNodeDeep() ;
+
+        // Either-Or
+//        promotePage(path, this) ;
+//        promote1(y, this, idx) ;
+        // Includes promote "this" because "this" is in the path.
+        promotePage(path, y) ;
+
+        Record splitKey = y.getSplitKey() ;
+        splitKey = keyRecord(splitKey) ;
+
+        if ( logging(log) )
+            log(log, "Split key: %s", splitKey) ;
+
+        BPTreePage z = y.split() ;
+        if ( logging(log) ) {
+            log(log, "Split: %s", y) ;
+            log(log, "Split: %s", z) ;
+        }
+
+        // Key only.
+        if ( splitKey.hasSeparateValue() )
+            splitKey = keyRecord(splitKey) ;
+
+        // Insert new node. "add" shuffle's up as well.
+        records.add(idx, splitKey) ;
+        ptrs.add(idx + 1, z.getId()) ;
+        count++ ;
+
+        if ( logging(log) ) {
+            log(log, "split <<   %s", this) ;
+            log(log, "split <<   %s", y) ;
+            log(log, "split <<   %s", z) ;
+        }
+
+        y.write() ;
+        z.write() ;
+        z.release() ;
+        // y.release() ; y release management done by caller.
+        this.write() ;
+        if ( BPT.CheckingNode ) {
+            if ( Record.keyNE(splitKey, y.maxRecord()) )
+                BPT.error("Split key %d but max subtree %s", splitKey, y.maxRecord()) ;
+            internalCheckNodeDeep() ;
+        }
+    }
+
+    @Override
+    final Record getSplitKey() {
+        int ix = params.SplitIndex ;
+        Record split = records.get(ix) ;
+        return split ;
+    }
+
+    /** Split this block - return the split record (key only needed) */
+    @Override
+    final BPTreePage split() {
+        // Median record : will go in parent.
+        int ix = params.SplitIndex ;
+
+        // New block.
+        BPTreeNode z = create(this.parent, isLeaf) ;
+
+        // Leave the low end untouched and copy, and clear the high end.
+        // z becomes the new upper node, not the lower node.
+        // 'this' is the lower block.
+
+        int maxRec = maxRecords() ;
+        // Copy from top of y into z.
+        records.copy(ix + 1, z.records, 0, maxRec - (ix + 1)) ;
+        records.clear(ix, maxRec - ix) ; // Clear copied and median slot
+        records.setSize(ix) ; // Reset size
+
+        ptrs.copy(ix + 1, z.ptrs, 0, params.MaxPtr - (ix + 1)) ;
+        ptrs.clear(ix + 1, params.MaxPtr - (ix + 1)) ;
+        ptrs.setSize(ix + 1) ;
+
+        // Set sizes of subnodes
+        setCount(ix) ; // Median is ix
+        internalCheckNode() ; // y finished
+
+        z.isLeaf = isLeaf ;
+        z.setCount(maxRec - (ix + 1)) ; // Number copied into z
+
+        // Caller puts the blocks in split(int, BTreePage)
+        z.internalCheckNode() ;
+        return z ;
+    }
+
+    /*
+     * Split the root and leave the root block as the root.
+     * This is the only point the height of the tree increases.
+     * 
+     * Allocate new blocks.
+     * Copy root low into left
+     * Copy root high into right
+     * Set counts.
+     * Create new root settings (two pointers, one key record)
+     * WRITE(left)
+     * WRITE(right)
+     * WRITE(root)
+     */
+    private static void splitRoot(BPTreeNode root) {
+        BPlusTree bpTree = root.bpTree ;
+
+        if ( BPT.CheckingNode )
+            if ( ! root.isRoot() )
+                BPT.error("Not root: %d (root is id zero)", root.getId()) ;
+        root.internalCheckNode() ;
+        promoteRoot(root) ;
+
+        // Median record
+        int splitIdx = root.params.SplitIndex ;
+        Record rec = root.records.get(splitIdx) ;
+
+        if ( logging(log) ) {
+            log(log, "** Split root %d (%s)", splitIdx, rec) ;
+            log(log, "splitRoot >>   %s", root) ;
+        }
+
+        // New blocks.
+        BPTreeNode left = create(bpTree, root.getId(), root.isLeaf) ;
+        BPTreeNode right = create(bpTree, root.getId(), root.isLeaf) ;
+
+        // int maxRecords = maxRecords() ;
+
+        // New left
+        root.records.copy(0, left.records, 0, splitIdx) ;
+        root.ptrs.copy(0, left.ptrs, 0, splitIdx + 1) ;
+        left.count = splitIdx ;
+
+        // New right
+        root.records.copy(splitIdx + 1, right.records, 0, root.maxRecords() - (splitIdx + 1)) ;
+        root.ptrs.copy(splitIdx + 1, right.ptrs, 0, root.params.MaxPtr - (splitIdx + 1)) ;
+        right.count = root.maxRecords() - (splitIdx + 1) ;
+
+        if ( logging(log) ) {
+            log(log, "splitRoot -- left:   %s", left) ;
+            log(log, "splitRoot -- right:  %s", right) ;
+        }
+
+        // So left.count+right.count = bTree.NumRec-1
+
+        // Clear root by reformatting. New root not a leaf. Has count of 1 after
+        // formatting.
+        BPTreeNodeMgr.formatForRoot(root, false) ;
+        // Make a non-leaf.
+
+        // Insert two subnodes, divided by the median record
+        root.count = 1 ;
+
+        root.records.add(0, rec) ;
+        root.ptrs.setSize(2) ;
+        root.ptrs.set(0, left.getId()) ; // slot 0
+        root.ptrs.set(1, right.getId()) ; // slot 1
+
+        if ( logging(log) ) {
+            log(log, "splitRoot <<   %s", root) ;
+            log(log, "splitRoot <<   %s", left) ;
+            log(log, "splitRoot <<   %s", right) ;
+        }
+
+        left.write() ;
+        right.write() ;
+        left.release() ;
+        right.release() ;
+        root.write() ;
+
+        if ( BPT.CheckingNode ) {
+            root.internalCheckNode() ;
+            left.internalCheckNode() ;
+            right.internalCheckNode() ;
+        }
+    }
+
+    // ============ DELETE
+
+    /*
+     * Delete
+     * Descend, making sure that the node is not minimum size at each descend.
+     * If it is, rebalenace.
+     */
+
+    @Override
+    final Record internalDelete(AccessPath path, Record rec) {
+        if ( logging(log) )
+            log(log, ">> internalDelete(%s) : %s", rec, this) ;
+        internalCheckNode() ;
+
+        int x = findSlot(rec) ;
+        int y = apply(x) ;
+        BPTreePage page = get(y) ;
+        trackPath(path, this, y, page) ;
+
+        if ( page.isMinSize() ) { 
+            // Ensure that a node is at least min+1 so a delete can happen.
+            // Can't be the root - we decended in the get().
+            rebalance(path, page, y) ;  // Ignore return - need to refind.
+            page.release(); // TODO But rebalance may have freed this?
+            // Rebalance may have moved the record due to shuffling.  
+            x = findSlot(rec) ;
+            y = apply(x) ;
+            page = get(y) ;
+            promote1(page, this, y) ;
+            resetTrackPath(path, this, y, page) ;
+            if ( BPT.CheckingNode ) {
+                internalCheckNode() ;
+                page.checkNode() ;
+            }
+            this.write() ;
+            // Needed in case the record being deleted is not in the
+            // tree, which mean there is no work done and
+            // this page is not written.
+            page.write() ;
+        }
+
+        // Go to bottom
+        // Need to return the deleted key/value.
+        Record r2 = page.internalDelete(path, rec) ;
+        if ( x >= 0 ) {
+            // And hence r2 != null.
+            // The deleted key was in the tree as well as the records.
+            // Change to the new key for the subtree. 
+            // Path is already promoted by the delete. 
+            // promote1(this, ??, ??) ;
+            Record mx = page.maxRecord() ;
+            records.set(x, keyRecord(mx)) ;
+            this.write() ;
+        }
+        if ( logging(log) )
+            log(log, "<< internalDelete(%s) : %s", rec, this) ;
+
+        page.release() ;
+        return r2 ;
+    }
+
+    /*
+     * Reduce the root when it has only one pointer and no records.
+     * WRITE(root)
+     * RELEASE(old child)
+     * This is the only point the height of the tree decreases.
+     */
+
+    private static void reduceRoot(BPTreeNode root) {
+        if ( logging(log) )
+            log(log, "reduceRoot >> %s", root) ;
+
+        if ( BPT.CheckingNode && (!root.isRoot() || root.count != 0) )
+            BPT.error("Not an empty root") ;
+
+        if ( root.isLeaf ) {
+            if ( logging(log) )
+                log(log, "reduceRoot << leaf root") ;
+            return ;
+        }
+
+        // Must have been cloned due to delete lower down
+        promoteRoot(root) ;
+        
+        BPTreePage sub = root.get(0) ;
+        promote1(sub, root, 0) ;
+        BPTreeNode n = cast(sub) ;
+        // Can pull up into the root.
+        // Leave root node in same block (rather than swap to new root).
+        BPTreeNodeMgr.formatForRoot(root, n.isLeaf) ;
+        n.records.copy(0, root.records, 0, n.count) ;
+        n.ptrs.copy(0, root.ptrs, 0, n.count + 1) ;
+        root.isLeaf = n.isLeaf ;
+        root.count = n.count ;
+        root.write() ;
+        // Free up.
+        n.free() ;
+        if ( BPT.CheckingNode )
+            root.internalCheckNodeDeep() ;
+
+        if ( logging(log) )
+            log(log, "reduceRoot << %s", root) ;
+    }
+
+    /*
+     * Rebalance "node" at slot idx in parent (this)
+     * The node will then be greater than the minimum size
+     * and one-pass delete is then possible.
+     * 
+     * try to shift right, from the left sibling (if exists)
+     * WRITE(left)
+     * WRITE(n)
+     * WRITE(this)
+     * try to shift left, from the right sibling (if exists)
+     * WRITE(right)
+     * WRITE(n)
+     * WRITE(this)
+     * else
+     * merge with left or right sibling
+     * Suboperations do all the write-back of nodes.
+     * 
+     * return the page which might be coalesced from left or right..
+     */
+    private BPTreePage rebalance(AccessPath path, BPTreePage node, int idx) {
+        if ( logging(log) ) {
+            log(log, "rebalance(id=%d, idx=%d)", node.getId(), idx) ;
+            log(log, ">> this: %s", this) ;
+            log(log, ">> node: %s", node) ;
+        }
+        internalCheckNode() ;
+//        promotePage(path, this) ;
+//        promote1(node, this, idx) ;
+        // Includes promote "this"
+        promotePage(path, node) ;
+
+        // Try left first
+        BPTreePage left = null ;
+        if ( idx > 0 )
+            left = get(idx - 1) ;
+
+        // *** SHIFTING : need to change the marker record in the parent.
+        // *** getHighRecord of lower block.
+
+        if ( left != null && !left.isMinSize() ) {
+            if ( logging(log) )
+                log(log, "rebalance/shiftRight") ;
+            // Move elements around.
+            promote1(left, this, idx-1) ;
+            
+            shiftRight(left, node, idx - 1) ;
+
+            if ( logging(log) )
+                log(log, "<< rebalance: %s", this) ;
+            if ( BPT.CheckingNode ) {
+                left.checkNode() ;
+                node.checkNode() ;
+                this.internalCheckNode() ;
+            }
+            left.release() ;
+            return node ;
+        }
+
+        BPTreePage right = null ;
+        if ( idx < count )
+            right = get(idx + 1) ;
+
+        if ( right != null && !right.isMinSize() ) {
+            if ( logging(log) )
+                log(log, "rebalance/shiftLeft") ;
+            
+            promote1(right, this, idx+1) ;
+            
+            shiftLeft(node, right, idx) ;
+
+            if ( logging(log) )
+                log(log, "<< rebalance: %s", this) ;
+            if ( BPT.CheckingNode ) {
+                right.checkNode() ;
+                node.checkNode() ;
+                this.internalCheckNode() ;
+            }
+            if ( left != null )
+                left.release() ;
+            right.release() ;
+            return node ;
+        }
+
+        // Couldn't shift. Collapse two pages.
+        if ( BPT.CheckingNode && left == null && right == null )
+            BPT.error("No siblings") ;
+
+        if ( left != null ) {
+            promote1(left, this, idx-1 ) ;
+            if ( logging(log) )
+                log(log, "rebalance/merge/left: left=%d n=%d [%d]", left.getId(), node.getId(), idx - 1) ;
+            if ( BPT.CheckingNode && left.getId() == node.getId() )
+                BPT.error("Left and n the same: %s", left) ;
+            BPTreePage page = merge(left, node, idx - 1) ;
+            if ( right != null )
+                // HACK : We didn't use it.
+                right.release() ;
+            //left release?
+            return page ;
+        } else {
+            // left == null
+            // rigth != null
+            promote1(right, this, idx+1 ) ;
+            // TODO ** HERE is it tracked correctly? Turmn tracking on, test_clear_02 and enable read checking in   Lifecycle track.free.
+            if ( logging(log) )
+                log(log, "rebalance/merge/right: n=%d right=%d [%d]", node.getId(), right.getId(), idx) ;
+            if ( BPT.CheckingNode && right.getId() == node.getId() )
+                BPT.error("N and right the same: %s", right) ;
+            BPTreePage page = merge(node, right, idx) ;
+            return page ;
+        }
+    }
+
+    /** Merge left with right ; fills left, frees right */
+    private BPTreePage merge(BPTreePage left, BPTreePage right, int dividingSlot) {
+        if ( logging(log) ) {
+            log(log, ">> merge(@%d): %s", dividingSlot, this) ;
+            log(log, ">> left:  %s", left) ;
+            log(log, ">> right: %s", right) ;
+        }
+
+        // /==\ + key + /==\ ==> /====\
+        Record splitKey = records.get(dividingSlot) ;
+        BPTreePage page = left.merge(right, splitKey) ;
+        // Must release right (not done in merge)
+        if ( logging(log) )
+            log(log, "-- merge: %s", page) ;
+
+        left.write() ;
+        left.release() ;
+        right.free() ;
+
+        if ( page == right )
+            BPT.error("Returned page is not the left") ;
+
+        if ( BPT.CheckingNode ) {
+            if ( isLeaf ) {
+                // If two data blocks, then the split key is not included
+                // (it's already there, with its value).
+                // Size is N+N and max could be odd so N+N and N+N+1 are
+                // possible.
+                if ( left.getCount() + 1 != left.getMaxSize() && left.getCount() != left.getMaxSize() )
+                    BPT.error("Inconsistent data node size: %d/%d", left.getCount(), left.getMaxSize()) ;
+            } else if ( !left.isFull() ) {
+                // If not two data blocks, the left side should now be full
+                // (N+N+split)
+                BPT.error("Inconsistent node size: %d/%d", left.getCount(), left.getMaxSize()) ;
+            }
+        }
+
+        // Remove from parent (which is "this")
+        shuffleDown(dividingSlot) ;
+        this.write() ;
+        internalCheckNodeDeep() ;
+        if ( logging(log) ) {
+            log(log, "<< merge: %s", this) ;
+            log(log, "<< left:  %s", left) ;
+        }
+        return left ;
+    }
+
+    @Override
+    BPTreePage merge(BPTreePage right, Record splitKey) {
+        return merge(this, splitKey, cast(right)) ;
+    }
+
+    private static BPTreeNode merge(BPTreeNode left, Record splitKey, BPTreeNode right) {
+        // Merge blocks - does not adjust the parent.
+        // Copy right to top of left.
+        // Caller releases 'right' (needed for testing code).
+
+        left.records.add(splitKey) ;
+
+        // Copy over right to top of left.
+        right.records.copyToTop(left.records) ;
+        right.ptrs.copyToTop(left.ptrs) ;
+
+        // Update count
+        left.count = left.count + right.count + 1 ;
+        left.internalCheckNode() ;
+
+        right.records.clear() ;
+        right.ptrs.clear() ;
+        return left ;
+    }
+
+    private void shiftRight(BPTreePage left, BPTreePage right, int i) {
+        if ( logging(log) ) {
+            log(log, ">> shiftRight: this:  %s", this) ;
+            log(log, ">> shiftRight: left:  %s", left) ;
+            log(log, ">> shiftRight: right: %s", right) ;
+        }
+        Record r1 = records.get(i) ;
+        Record r2 = left.shiftRight(right, r1) ;
+        r2 = keyRecord(r2) ;
+        this.records.set(i, r2) ;
+
+        left.write() ;
+        right.write() ;
+        // Do later -- this.put();
+        if ( logging(log) ) {
+            log(log, "<< shiftRight: this:  %s", this) ;
+            log(log, "<< shiftRight: left:  %s", left) ;
+            log(log, "<< shiftRight: right: %s", right) ;
+        }
+    }
+
+    private void shiftLeft(BPTreePage left, BPTreePage right, int i) {
+        if ( logging(log) ) {
+            log(log, ">> shiftLeft: this:  %s", this) ;
+            log(log, ">> shiftLeft: left:  %s", left) ;
+            log(log, ">> shiftLeft: right: %s", right) ;
+        }
+        Record r1 = records.get(i) ;
+        Record r2 = left.shiftLeft(right, r1) ;
+        r2 = keyRecord(r2) ;
+        this.records.set(i, r2) ;
+
+        left.write() ;
+        right.write() ;
+        // Do this later - this.put();
+        if ( logging(log) ) {
+            log(log, "<< shiftLeft: this:  %s", this) ;
+            log(log, "<< shiftLeft: left:  %s", left) ;
+            log(log, "<< shiftLeft: right: %s", right) ;
+        }
+    }
+
+    @Override
+    Record shiftRight(BPTreePage other, Record splitKey) {
+        BPTreeNode node = cast(other) ;
+        if ( BPT.CheckingNode ) {
+            if ( count == 0 )
+                BPT.error("Node is empty - can't shift a slot out") ;
+            if ( node.isFull() )
+                BPT.error("Destination node is full") ;
+        }
+        // Records: promote moving element, replace with splitKey
+        Record r = this.records.getHigh() ;
+        this.records.removeTop() ;
+        node.records.add(0, splitKey) ;
+
+        // Pointers just shift
+        this.ptrs.shiftRight(node.ptrs) ;
+
+        this.count-- ;
+        node.count++ ;
+        this.internalCheckNode() ;
+        node.internalCheckNode() ;
+        return r ;
+    }
+
+    @Override
+    Record shiftLeft(BPTreePage other, Record splitKey) {
+        BPTreeNode node = cast(other) ;
+        if ( BPT.CheckingNode ) {
+            if ( count == 0 )
+                BPT.error("Node is empty - can't shift a slot out") ;
+            if ( isFull() )
+                BPT.error("Destination node is full") ;
+        }
+        Record r = node.records.getLow() ;
+        // Records: promote moving element, replace with splitKey
+        this.records.add(splitKey) ;
+        node.records.shiftDown(0) ;
+
+        // Pointers just shift
+        this.ptrs.shiftLeft(node.ptrs) ;
+
+        this.count++ ;
+        node.count-- ;
+        return r ;
+    }
+
+    private void shuffleDown(int x) {
+        // x is the index in the parent and may be on eover the end.
+        if ( logging(log) ) {
+            log(log, "ShuffleDown: i=%d count=%d MaxRec=%d", x, count, maxRecords()) ;
+            log(log, "ShuffleDown >> %s", this) ;
+        }
+
+        if ( BPT.CheckingNode && x >= count )
+            BPT.error("shuffleDown out of bounds") ;
+
+        // Just the top to clear
+
+        if ( x == count - 1 ) {
+            records.removeTop() ;
+            ptrs.removeTop() ;
+
+            count-- ;
+            if ( logging(log) ) {
+                log(log, "shuffleDown << Clear top") ;
+                log(log, "shuffleDown << %s", this) ;
+            }
+            internalCheckNode() ;
+            return ;
+        }
+
+        // Shuffle down. Removes key and pointer just above key.
+
+        records.shiftDown(x) ;
+        ptrs.shiftDown(x + 1) ;
+        count-- ;
+        if ( logging(log) )
+            log(log, "shuffleDown << %s", this) ;
+        internalCheckNode() ;
+    }
+
+    // ---- Utilities
+
+    private static final BPTreeNode cast(BPTreePage other) {
+        try {
+            return (BPTreeNode)other ;
+        }
+        catch (ClassCastException ex) {
+            BPT.error("Wrong type: " + other) ;
+            return null ;
+        }
+    }
+
+    final int findSlot(Record rec) {
+        int x = records.find(rec) ;
+        return x ;
+    }
+
+    final boolean isRoot() {
+        // No BPT remembered root node currently
+        // if ( bpTree.root == this ) return true ;
+        return this.parent == BPlusTreeParams.RootParent ;
+    }
+
+    private Record keyRecord(Record record) {
+        return bpTree.getRecordFactory().createKeyOnly(record) ;
+    }
+
+    // Fixup/remove?
+    private final int maxRecords() {
+        return params.MaxRec ;
+    }
+
+    @Override
+    final boolean isFull() {
+        if ( BPT.CheckingNode && count > maxRecords() )
+            BPT.error("isFull: Moby block: %s", this) ;
+
+        // Count is number of records.
+        return count >= maxRecords() ;
+    }
+    
+    /** Return true if there are no keys here or below this node */
+    @Override
+    final boolean hasAnyKeys() {
+        if ( this.count > 0 )
+            return true ;
+        if ( !isRoot() )
+            return false ;
+
+        // The root can be zero size and point to a single data block.
+        BPTreePage page = get(0) ;
+        boolean b = page.hasAnyKeys() ;
+        page.release() ;
+        return b ;
+    }
+
+    @Override
+    final boolean isMinSize() {
+        int min = params.getMinRec() ;
+        if ( BPT.CheckingNode && count < min )
+            BPT.error("isMinSize: Dwarf block: %s", this) ;
+
+        return count <= min ;
+    }
+
+    // ========== Other
+
+    @Override
+    public String toString() {
+        StringBuilder b = new StringBuilder() ;
+        if ( isLeaf )
+            b.append("LEAF: ") ;
+        else
+            b.append("NODE: ") ;
+        String labelStr = "??" ;
+        if ( parent >= 0 )
+            labelStr = Integer.toString(parent) ;
+        else if ( parent == BPlusTreeParams.RootParent )
+            labelStr = "root" ;
+        if ( isLeaf )
+            labelStr = labelStr + "/leaf" ;
+
+        b.append(String.format("%d [%s] (size %d) -- ", getId(), labelStr, count)) ;
+        for ( int i = 0 ; i < maxRecords() ; i++ ) {
+            b.append(childStr(i)) ;
+            b.append(" (") ;
+            b.append(recstr(records, i)) ;
+            b.append(") ") ;
+        }
+        b.append(childStr(params.HighPtr)) ;
+        return b.toString() ;
+    }
+
+    @Override
+    protected String typeMark() {
+        String mark = isLeaf() ? "Leaf" : "Node" ;
+        if ( isRoot() )
+            mark = mark+"/Root" ;
+        return mark ; 
+    }
+
+    private final String recstr(RecordBuffer records, int idx) {
+        if ( records.isClear(idx) )
+            return "----" ;
+
+        Record r = records._get(idx) ;
+        return r.toString() ;
+    }
+
+    public void dump() {
+        boolean b = BPT.Logging ;
+        BPT.Logging = false ;
+        try { dump(IndentedWriter.stdout) ; }
+        finally { BPT.Logging = b ; }
+    }
+
+    public void dump(IndentedWriter out) {
+        output(out) ;
+        out.ensureStartOfLine() ;
+        out.flush() ;
+    }
+
+    public String dumpToString() {
+        IndentedLineBuffer buff = new IndentedLineBuffer() ;
+        output(buff) ;
+        return buff.asString() ;
+    }
+
+    @Override
+    public void output(IndentedWriter out) {
+        out.print(toString()) ;
+        out.incIndent() ;
+        for ( int i = 0 ; i < count + 1 ; i++ ) {
+            out.println() ;
+            BPTreePage page = get(i) ;
+            page.output(out) ;
+            page.release() ;
+
+        }
+        out.decIndent() ;
+    }
+
+    private String childStr(int i) {
+        if ( i >= ptrs.size() )
+            return "*" ;
+        int x = ptrs.get(i) ;
+        return Integer.toString(x) ;
+    }
+
+    // =========== Checking
+    // internal checks - only if checking
+
+    // Check node does not assume a valid tree - may be in mid-operation.
+    private final void internalCheckNode() {
+        if ( BPT.CheckingNode )
+            checkNode(null, null) ;
+    }
+
+    private final void internalCheckNodeDeep() {
+        // This distrubes trackign operations and blocks.
+        // Hooks left but switch off.
+        if ( false )
+            checkNodeDeep() ;
+    }
+
+    @Override
+    final void checkNode() {
+        checkNode(null, null) ;
+    }
+
+    @Override
+    final void checkNodeDeep() {
+        if ( isRoot() ) {
+            // if ( !isLeaf && count == 0 )
+            // error("Root is of size zero (one pointer) but not a leaf") ;
+            if ( parent != BPlusTreeParams.RootParent )
+                BPT.error("Root parent is wrong") ;
+            // if ( count == 0 )
+            // return ;
+        }
+        checkNodeDeep(null, null) ;
+    }
+
+    // Checks of a single node - no looking at children
+    // min - inclusive; max - inclusive (allows for duplicates)
+    final private void checkNode(Record min, Record max) {
+        int id = getId() ;
+        if ( count != records.size() )
+            BPT.error("Inconsistent: id=%d, count=%d, records.size()=%d : %s", id, count, records.size(), this) ;
+
+        if ( !isLeaf && count + 1 != ptrs.size() )
+            BPT.error("Inconsistent: id=%d, count+1=%d, ptrs.size()=%d ; %s", id, count + 1, ptrs.size(), this) ;
+
+        // No BPT remembered root node currently
+        // if ( bpTree.root != null && !isRoot() && count < params.MinRec)
+        if ( !isRoot() && count < params.MinRec ) {
+            // warning("Runt node: %s", this) ;
+            BPT.error("Runt node: %s", this) ;
+        }
+        if ( !isRoot() && count > maxRecords() )
+            BPT.error("Over full node: %s", this) ;
+        if ( !isLeaf && parent == id )
+            BPT.error("Parent same as id: %s", this) ;
+        Record k = min ;
+
+        // Test records in the allocated area
+        for ( int i = 0 ; i < count ; i++ ) {
+            if ( records.get(i) == null )
+                BPT.error("Node: %d : Invalid record @%d :: %s", id, i, this) ;
+            if ( k != null && keyGT(k, records.get(i)) ) {
+                Record r = records.get(i) ;
+                // keyGT(k, r) ;
+                BPT.error("Node: %d: Not sorted (%d) (%s, %s) :: %s ", id, i, k, r, this) ;
+            }
+            k = records.get(i) ;
+        }
+
+        if ( k != null && max != null && keyGT(k, max) )
+            BPT.error("Node: %d - Record is too high (max=%s):: %s", id, max, this) ;
+
+        if ( SystemIndex.getNullOut() ) {
+            // Test records in the free area
+            for ( int i = count ; i < maxRecords() ; i++ ) {
+                if ( !records.isClear(i) )
+                    BPT.error("Node: %d - not clear (idx=%d) :: %s", id, i, this) ;
+            }
+        }
+
+        // Pointer checks.
+        int i = 0 ;
+        // Check not empty at bottom.
+        for ( ; i < count + 1 ; i++ ) {
+            if ( ptrs.get(i) < 0 )
+                BPT.error("Node: %d: Invalid child pointer @%d :: %s", id, i, this) ;
+//            // This does Block IO so disturbs tracking.
+//            if ( BPT.CheckingTree && isLeaf ) {
+//                int ptr = ptrs.get(i) ;
+//                BPTreeRecords records = bpTree.getRecordsMgr().getRead(ptr) ;
+//                int rid = records.getId() ;
+//                if ( rid != ptrs.get(i) )
+//                    BPT.error("Records: Block @%d has a different id: %d :: %s", rid, i, this) ;
+//                int link = records.getLink() ;
+//                // Don't check if -1 which does not exist.
+//                if ( link != -1 && i != count ) {
+//                    BPTreeRecords page = bpTree.getRecordsMgr().getRead(ptrs.get(i)) ;
+//                    int rid2 = page.getLink() ;
+//                    if ( link != rid2 )
+//                        BPT.error("Records: Link not to next block @%d/@%d has a different id: %d :: %s", rid, rid2, i, records) ;
+//                    bpTree.getRecordsMgr().release(page) ;
+//                }
+//                records.release() ;
+//            }
+        }
+
+        // Check empty is empty
+        if ( SystemIndex.getNullOut() ) {
+            int x = params.MaxPtr ;
+            for ( ; i < x ; i++ ) {
+                if ( !ptrs.isClear(i) )
+                    BPT.error("Node: %d: Unexpected pointer @%d :: %s", id, i, this) ;
+            }
+        }
+    }
+
+    private void checkNodeDeep(Record min, Record max) {
+        checkNode(min, max) ;
+        int id = getId() ;
+        // Check pointers.
+        int limit = (count == 0) ? 0 : count + 1 ;
+
+        for ( int i = 0 ; i < limit ; i++ ) {
+            Record min1 = min ;
+            Record max1 = max ;
+            BPTreePage n = get(i) ;
+
+            if ( i != count ) {
+                Record keySubTree = n.getHighRecord() ; // high key in immediate
+                                                        // child
+                Record keyHere = records.get(i) ; // key in this
+
+                if ( keySubTree == null )
+                    BPT.error("Node: %d: Can't get high record from %d", id, n.getId()) ;
+
+                if ( keySubTree.getKey() == null )
+                    BPT.error("Node: %d: Can't get high record is missing it's key from %d", id, n.getId()) ;
+
+                if ( keyHere == null )
+                    BPT.error("Node: %d: record is null", id) ;
+
+                if ( keyHere.getKey() == null )
+                    BPT.error("Node: %d: Record key is null", id) ;
+
+                if ( keyGT(keySubTree, keyHere) )
+                    BPT.error("Node: %d: Child key %s is greater than this key %s", id, keySubTree, keyHere) ;
+
+                Record keyMax = n.maxRecord() ; // max key in subTree
+                Record keyMin = n.internalMinRecord(null) ;
+
+                if ( keyNE(keyHere, keyMax) )
+                    BPT.error("Node: %d: Key %s is not the max [%s] of the sub-tree idx=%d", id, keyHere, keyMax, i) ;
+
+                if ( min != null && keyGT(min, keyMin) )
+                    BPT.error("Node: %d: Minimun for this node should be %s but it's %s", id, min, keyMin) ;
+                if ( max != null && keyLT(max, keyMax) )
+                    BPT.error("Node: %d: Maximum for this node should be %s but it's %s", id, max, keyMax) ;
+                if ( min != null && keyGT(min, keyHere) )
+                    BPT.error("Node: %d: Key too small: %s - min should be %s", id, keyHere, min) ;
+                // keyHere == keyMax ??
+                if ( max != null && keyLT(max, keyHere) )
+                    BPT.error("Node: %d: Key too large: %s - max should be %s", id, keyHere, max) ;
+            }
+
+            // Look deeper.
+            if ( !(n instanceof BPTreeNode) ) {
+                // Records.
+                n.checkNodeDeep() ;
+                n.release() ;
+                continue ;
+            }
+
+            // Valid pointer?
+            if ( isLeaf ) {
+                if ( !bpTree.getRecordsMgr().getBlockMgr().valid(ptrs.get(i)) )
+                    BPT.error("Node: %d: Dangling ptr (records) in block @%d :: %s", id, i, this) ;
+            } else {
+                if ( !bpTree.getNodeManager().valid(ptrs.get(i)) )
+                    BPT.error("Node: %d: Dangling ptr in block @%d :: %s", id, i, this) ;
+            }
+
+            // Calc new min/max.
+            if ( i == 0 )
+                max1 = records.get(0) ;
+            else if ( i == count ) {
+                min1 = records.get(count - 1) ;
+                max1 = null ;
+            } else {
+                min1 = records.get(i - 1) ;
+                max1 = records.get(i) ;
+            }
+            // if ( n.parent != id )
+            // error("Node: %d [%d]: Parent/child mismatch :: %s", id, n.parent,
+            // this) ;
+
+            ((BPTreeNode)n).checkNodeDeep(min1, max1) ;
+            n.release() ;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNodeMgr.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNodeMgr.java b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNodeMgr.java
new file mode 100644
index 0000000..2d542ed
--- /dev/null
+++ b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeNodeMgr.java
@@ -0,0 +1,229 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.dboe.trans.bplustree;
+
+import static org.apache.jena.dboe.base.block.BlockType.BPTREE_BRANCH;
+import static org.apache.jena.dboe.base.block.BlockType.BPTREE_LEAF;
+import static org.apache.jena.dboe.base.block.BlockType.RECORD_BLOCK;
+
+import java.nio.ByteBuffer ;
+
+import org.apache.jena.dboe.base.block.Block;
+import org.apache.jena.dboe.base.block.BlockMgr;
+import org.apache.jena.dboe.base.block.BlockType;
+import org.apache.jena.dboe.base.buffer.PtrBuffer;
+import org.apache.jena.dboe.base.buffer.RecordBuffer;
+import org.apache.jena.dboe.base.page.BlockConverter;
+import org.apache.jena.dboe.base.page.PageBlockMgr;
+
+/** BPlusTreePageMgr = BPlusTreeNode manager */
+public final class BPTreeNodeMgr extends PageBlockMgr<BPTreeNode>
+{
+    // Only "public" for external very low level tools in development to access this class.
+    // Assume package access.
+
+    public BPTreeNodeMgr(BPlusTree bpTree, BlockMgr blockMgr) {
+        super(new Block2BPTreeNode(bpTree), blockMgr) ;
+    }
+   
+    /** Allocate space for a fresh node. */
+    public BPTreeNode createNode(int parent) {
+        BPTreeNode n = create(BPTREE_BRANCH) ;
+        n.setIsLeaf(false) ;
+        n.setParent(parent) ;
+        return n ;
+    }
+
+    @Override
+    public BPTreeNode getWrite(int id) {
+        return super.getWrite(id, BPlusTreeParams.UnsetParent) ;
+    }
+
+    @Override
+    public BPTreeNode getRead(int id) {
+        return super.getRead(id, BPlusTreeParams.UnsetParent) ;
+    }
+
+    /** Fetch a block - fill in the parent id, which is not in the on-disk bytes */
+    @Override
+    public BPTreeNode getRead(int id, int parent) {
+        BPTreeNode n = super.getRead$(id) ;
+        n.setParent(parent);
+        return n ;
+    }
+
+    /** Fetch a block - fill in the parent id, which is not in the on-disk bytes */
+    @Override
+    public BPTreeNode getWrite(int id, int parent) {
+        BPTreeNode n = super.getWrite$(id) ;
+        n.setParent(parent);
+        return n ;
+    }
+
+    boolean isWritable(int id) {
+        //System.err.println("BPTreeNodeMgr.isWritable") ;
+        return false ;
+//      return bpTree.state.modifiableNodeBlock(id) ;
+    }
+
+    private static class Block2BPTreeNode implements BlockConverter<BPTreeNode>
+    {
+        private final BPlusTree bpTree ;
+
+        Block2BPTreeNode(BPlusTree bpTree) { this.bpTree = bpTree ; }
+        
+        @Override
+        public BPTreeNode createFromBlock(Block block, BlockType bType) {
+            return overlay(bpTree, block, bType == RECORD_BLOCK, 0) ;
+        }
+
+        @Override
+        public BPTreeNode fromBlock(Block block) {
+            // synchronized - needed for multiple reader?
+            synchronized (block) {
+                int x = block.getByteBuffer().getInt(0) ;
+                BlockType type = getType(x) ;
+
+                if ( type != BPTREE_BRANCH && type != BPTREE_LEAF )
+                    throw new BPTreeException("Wrong block type: " + type) ;
+                int count = decodeCount(x) ;
+                return overlay(bpTree, block, (type == BPTREE_LEAF), count) ;
+            }
+        }
+
+        @Override
+        public Block toBlock(BPTreeNode node) {
+            // It's manipulated in-place so no conversion needed, 
+            // Just the count needs to be fixed up. 
+//            ByteBuffer bb = node.getBackingByteBuffer() ;
+//            BlockType bType = (node.isLeaf ? BPTREE_LEAF : BPTREE_BRANCH ) ;
+
+            Block block = node.getBackingBlock() ;
+            BlockType bType = (node.isLeaf() ? BPTREE_LEAF : BPTREE_BRANCH ) ;
+
+            int c = encodeCount(bType, node.getCount()) ;
+            block.getByteBuffer().putInt(0, c) ;
+            return block ;
+        }
+    }
+    
+//    // Leaves have a count of -(count+1)
+//    // (same as the binary search encoding of "not found")
+//    private static final int encCount(int i)     { return -(i+1) ; } 
+//    private static final int decCount(int i)     { return -i-1 ; }
+
+    // ----
+    private static final BlockType getType(int x) {
+        return BlockType.extract(x >>> 24) ;
+    }
+
+    private static final int encodeCount(BlockType type, int i) {
+        return (type.id() << 24) | (i & 0x00FFFFFF) ;
+    }
+
+    private static final int decodeCount(int i) {
+        return i & 0x00FFFFFF ;
+    }
+
+    /** byte[] layout.
+     * 
+     * New:
+     *  0: Block type
+     *  1-3: Count 
+     *  Internal nodes:
+     *    4-X:        Records: b+tree.MaxRec*record length
+     *    X- :        Pointers: b+tree.MaxPtr*ptr length 
+     */
+    private static BPTreeNode overlay(BPlusTree bpTree, Block block, boolean asLeaf, int count) {
+        // if ( byteBuffer.order() != Const.NetworkOrder )
+        // throw new BTreeException("ByteBuffer in wrong order") ;
+
+        // Fix up the id later.
+        BPTreeNode n = new BPTreeNode(bpTree) ;
+        // The count is zero at the root only.
+        // When the root is zero, it's a leaf.
+        formatBPTreeNode(n, bpTree, block, asLeaf, BPlusTreeParams.NoParent, count) ;
+        return n ;
+    }
+
+    static void formatBPTreeNode(BPTreeNode n, BPlusTree bpTree, Block block, boolean leaf, int parent, int count) {
+        BPlusTreeParams params = bpTree.getParams() ;
+
+        int ptrBuffLen = params.MaxPtr * params.getPtrLength() ;
+        // Only store the key part of records in a B+Tree block
+        // OLD - Node table has real value part - what's going on?
+
+        // [Issue:FREC]
+        // Allocate space for record, key and value, despite slight over
+        // allocation.
+        int recBuffLen = params.MaxRec * params.getRecordLength() ;
+
+        // [Issue:FREC] Should be: key space only.
+        // int recBuffLen = params.MaxRec * params.getKeyLength() ;
+
+        n.id = block.getId().intValue() ;
+        n.setParent(parent) ;
+        n.setCount(count) ;
+        n.setIsLeaf(leaf) ;
+
+        int header = BPlusTreeParams.BlockHeaderSize ;
+        int rStart = header ;
+        int pStart = header + recBuffLen ;
+
+        // Find the number of pointers.
+        int numPtrs = -1 ;
+
+        // The root can have count zero - which means one pointer always.
+        // Junk when creating a new new node.
+        if ( n.getCount() < 0 ) {
+            numPtrs = 0 ;
+            n.setCount(decodeCount(n.getCount())) ;
+        } else
+            numPtrs = n.getCount() + 1 ;
+
+        // Block dependent
+        
+        n.block = block ;
+        ByteBuffer byteBuffer = block.getByteBuffer() ;
+
+        // -- Records area
+        byteBuffer.position(rStart) ;
+        byteBuffer.limit(rStart + recBuffLen) ;
+        ByteBuffer bbr = byteBuffer.slice() ;
+        // bbr.limit(recBuffLen) ;
+        n.setRecordBuffer(new RecordBuffer(bbr, n.params.keyFactory, n.getCount())) ;
+
+        // -- Pointers area
+        byteBuffer.position(pStart) ;
+        byteBuffer.limit(pStart + ptrBuffLen) ;
+
+        ByteBuffer bbi = byteBuffer.slice() ;
+        // bbi.limit(ptrBuffLen) ;
+        n.setPtrBuffer(new PtrBuffer(bbi, numPtrs)) ;
+
+        // Reset
+        byteBuffer.rewind() ;
+    }
+    
+    static final void formatForRoot(BPTreeNode n, boolean asLeaf) {
+        BPTreeNodeMgr.formatBPTreeNode(n, n.bpTree, n.getBackingBlock(), asLeaf, BPlusTreeParams.RootParent, 0) ;
+        // Tweak for the root-specials. The node is not consistent yet.
+        // Has one dangling pointer.
+    }
+}

http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreePage.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreePage.java b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreePage.java
new file mode 100644
index 0000000..a023718
--- /dev/null
+++ b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreePage.java
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.dboe.trans.bplustree;
+
+import org.apache.jena.dboe.base.block.BlockMgr;
+import org.apache.jena.dboe.base.page.Page;
+import org.apache.jena.dboe.base.record.Record;
+import org.slf4j.Logger ;
+
+/** Abstraction of a B+Tree node - either an branch (BTreeNode) or records block (BTreeRecords) */
+abstract public class BPTreePage implements Page
+{
+    protected BPTreePage(BPlusTree bpTree) {
+        this.bpTree = bpTree ;
+        // bpTree can be null in testing.
+        this.params = ( bpTree == null ) ? null : bpTree.getParams() ;
+    }
+    
+    protected final BPlusTree bpTree ; 
+    protected final BPlusTreeParams params ;
+
+    /** Short form for logging */
+    protected String label() {
+        return String.format("%d[%s]", getId(), typeMark()) ;
+    }
+    
+    protected abstract String typeMark() ;
+    
+    protected abstract Logger getLogger() ;
+    
+    abstract BlockMgr getBlockMgr() ;
+
+    /** Split in two, return the new (upper) page.  
+     *  Split key is highest key of the old (lower) page.
+     *  Does NOT put pages back to any underlying block manager
+     */ 
+    abstract BPTreePage split() ;
+    
+    /** Move the element from the high end of this to the low end of other,
+    *  possible including the splitKey
+     * Return the new split point (highest record in left tree for records; moved element for nodes)
+     */
+    abstract Record shiftRight(BPTreePage other, Record splitKey) ;
+    
+    /** Move the element from the high end of other to the high end of this, 
+     * possible including the splitKey
+     * Return the new split point (highest record in left tree; moved element for nodes)
+     */
+    abstract Record shiftLeft(BPTreePage other, Record splitKey) ;
+    
+    /** Merge this (left) and the page imemdiately to it's right other into a single block
+     */
+    abstract BPTreePage merge(BPTreePage right, Record splitKey) ;
+    //* Return the new page (may be left or right)
+    
+    /** Test whether this page is full (has no space for a new element) - used in "insert" */
+    abstract boolean isFull() ;
+    
+    /**  Test whether this page is of minimum size (removing a record would violate the packing limits) - used in "delete" */
+    abstract boolean isMinSize() ;
+    
+    abstract int getCount() ;
+    
+    abstract void setCount(int count) ;
+  
+    abstract int getMaxSize() ;
+    
+    /**  Test whether this page has any keys */
+    abstract boolean hasAnyKeys() ;
+
+    /** Find a record; return null if not found */
+    abstract Record internalSearch(AccessPath path, Record rec) ;
+    
+    /** Insert a record - return existing value if any, else null - put back modifed blocks */
+    abstract Record internalInsert(AccessPath path, Record record) ;
+    
+    /** Delete a record - return the old value if there was one, else null - put back modifed blocks */
+    abstract Record internalDelete(AccessPath path, Record record) ;
+
+    /** Least in page */
+    abstract Record getLowRecord() ;
+
+    /** Greatest in page */
+    abstract Record getHighRecord() ;
+
+    /** Least in subtree */
+    abstract Record internalMinRecord(AccessPath path) ;
+
+    /** Greatest in subtree */
+    abstract Record internalMaxRecord(AccessPath path) ;
+
+    // For checking ...
+    
+    /** Least in subtree */
+    Record minRecord()      { return internalMinRecord(null) ; } 
+
+    /** Greatest in subtree */
+    Record maxRecord()      { return internalMaxRecord(null) ; }
+    
+    /** Write, or at least ensure will be written */
+    abstract void write() ; 
+    
+    /** Turn a read page into a write page. Return true if any changes were made. */
+    abstract boolean promote() ;
+
+    /** Mark as no longer needed */
+    abstract void release() ;
+    
+    /** Discard with this block (for ever) */
+    abstract void free() ;
+
+    /** Check - just this level.*/
+    abstract void checkNode() ;
+    
+    /** Check - here and below */
+    abstract void checkNodeDeep() ;
+
+    /** Return the split point for this record (need only be a key)*/
+    abstract Record getSplitKey() ;
+}

http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRangeIterator.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRangeIterator.java b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRangeIterator.java
new file mode 100644
index 0000000..2ad1f23
--- /dev/null
+++ b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRangeIterator.java
@@ -0,0 +1,153 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.dboe.trans.bplustree;
+
+import java.util.* ;
+
+import org.apache.jena.atlas.iterator.Iter ;
+import org.apache.jena.atlas.lib.InternalErrorException ;
+import org.apache.jena.dboe.base.record.Record;
+import org.apache.jena.dboe.trans.bplustree.AccessPath.AccessStep;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+
+/** Iterator over records that does not assume records block linkage */ 
+class BPTreeRangeIterator implements Iterator<Record> {
+    static Logger log = LoggerFactory.getLogger(BPTreeRangeIterator.class) ;
+    
+    public static Iterator<Record> create(BPTreeNode node, Record minRec, Record maxRec) {
+        if ( minRec != null && maxRec != null && Record.keyGE(minRec, maxRec) )
+            return Iter.nullIter();
+        return new BPTreeRangeIterator(node, minRec, maxRec) ;
+    }
+    
+    // Convert path to a stack of iterators
+    private final Deque<Iterator<BPTreePage>> stack = new ArrayDeque<>();
+    final private Record minRecord ;
+    final private Record maxRecord ;
+    private Iterator<Record> current ;
+    private Record slot = null ;
+    private boolean finished = false ;
+    
+    BPTreeRangeIterator(BPTreeNode node, Record minRec, Record maxRec ) {
+        this.minRecord = minRec ;
+        this.maxRecord = maxRec ;
+        BPTreeRecords r = loadStack(node) ;
+        current = getRecordsIterator(r, minRecord, maxRecord) ;
+    }
+
+    @Override
+    public boolean hasNext() {
+        if ( finished ) 
+            return false ;
+        if ( slot != null )
+            return true ;
+        while(current != null && !current.hasNext()) {
+            current = moveOnCurrent() ;
+        } 
+        if ( current == null ) {
+            end() ;
+            return false ;
+        }
+        slot = current.next() ;
+        return true ;
+        
+    }
+    
+    // Move across the head of the stack until empty - then move next level. 
+    private Iterator<Record> moveOnCurrent() {
+        Iterator<BPTreePage> iter = null ;
+        while(!stack.isEmpty()) { 
+            iter = stack.peek() ;
+            if ( iter.hasNext() )
+              break ;
+            stack.pop() ;
+        } 
+        
+        if ( iter == null || ! iter.hasNext() )
+            return null ;
+        BPTreePage p = iter.next() ;
+        BPTreeRecords r = null ;
+        if (p instanceof BPTreeNode) {
+            r = loadStack((BPTreeNode)p) ;
+        }
+        else {
+            r = (BPTreeRecords)p ;
+        }
+        return getRecordsIterator(r, minRecord, maxRecord) ;
+    }
+    
+    // ---- Places we touch blocks. 
+    
+    private static Iterator<Record> getRecordsIterator(BPTreeRecords records, Record minRecord, Record maxRecord) {
+        records.bpTree.startReadBlkMgr();
+        Iterator<Record> iter = records.getRecordBuffer().iterator(minRecord, maxRecord) ;
+        records.bpTree.finishReadBlkMgr();
+        return iter ;
+    }
+    
+    private BPTreeRecords loadStack(BPTreeNode node) {
+        AccessPath path = new AccessPath(null) ;
+        node.bpTree.startReadBlkMgr();
+        
+        if ( minRecord == null )
+            node.internalMinRecord(path) ;
+        else
+            node.internalSearch(path, minRecord) ;
+        List<AccessStep> steps = path.getPath() ;
+        for ( AccessStep step : steps ) {
+            BPTreeNode n = step.node ; 
+            Iterator<BPTreePage> it = n.iterator(minRecord, maxRecord) ;
+            if ( it == null || ! it.hasNext() )
+                continue ;
+            BPTreePage p = it.next() ;
+            stack.push(it) ;
+        }
+        BPTreePage p = steps.get(steps.size()-1).page ;
+        if ( ! ( p instanceof BPTreeRecords ) )
+            throw new InternalErrorException("Last path step not to a records block") ;
+        node.bpTree.finishReadBlkMgr();
+        return (BPTreeRecords)p ;
+    }
+
+    // ---- 
+
+    private void end() {
+        finished = true ;
+        current = null ;
+    }
+    
+    // ---- 
+    
+    public void close() {
+        if ( ! finished )
+            end() ;
+    }
+
+    @Override
+    public Record next() {
+        if ( ! hasNext() )
+            throw new NoSuchElementException() ;
+        Record r = slot ;
+        if ( r == null )
+            throw new InternalErrorException("Null slot after hasNext is true") ;
+        slot = null ;
+        return r ;
+    }
+}

http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRecords.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRecords.java b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRecords.java
new file mode 100644
index 0000000..18030a1
--- /dev/null
+++ b/jena-db/jena-dboe-trans-data/src/main/java/org/apache/jena/dboe/trans/bplustree/BPTreeRecords.java
@@ -0,0 +1,389 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.dboe.trans.bplustree ;
+
+import static java.lang.String.format ;
+import static org.apache.jena.atlas.lib.Alg.decodeIndex ;
+import static org.apache.jena.dboe.trans.bplustree.BPT.CheckingNode;
+import static org.apache.jena.dboe.trans.bplustree.BPT.promotePage;
+
+import org.apache.jena.atlas.io.IndentedWriter ;
+import org.apache.jena.dboe.base.StorageException;
+import org.apache.jena.dboe.base.block.Block;
+import org.apache.jena.dboe.base.block.BlockMgr;
+import org.apache.jena.dboe.base.buffer.RecordBuffer;
+import org.apache.jena.dboe.base.page.Page;
+import org.apache.jena.dboe.base.record.Record;
+import org.apache.jena.dboe.base.recordbuffer.RecordBufferPage;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+
+/**
+ * B+Tree wrapper over a block of records in a RecordBufferPage.
+ * This class adds no persistent state to a RecordBufferPage.
+ */
+public final class BPTreeRecords extends BPTreePage {
+    private static Logger log = LoggerFactory.getLogger(BPTreeRecords.class) ;
+
+    @Override
+    protected Logger getLogger() {
+        return log ;
+    }
+
+    private final RecordBufferPage rBuffPage ;
+    private final BPTreeRecordsMgr bprRecordsMgr ;
+    private RecordBuffer           rBuff ;        // Used heavily. Derived from
+                                                   // rBuffPage
+
+    BPTreeRecords(BPTreeRecordsMgr mgr, RecordBufferPage rbp) {
+        super(mgr.getBPTree()) ;
+        this.bprRecordsMgr = mgr ;
+        rBuffPage = rbp ;
+        rBuff = rBuffPage.getRecordBuffer() ;
+    }
+
+    RecordBufferPage getRecordBufferPage() {
+        return rBuffPage ;
+    }
+
+    RecordBuffer getRecordBuffer() {
+        return rBuff ;
+    }
+
+    public final Record get(int idx) {
+        return rBuff.get(idx) ;
+    }
+
+    @Override
+    public final Block getBackingBlock() {
+        return rBuffPage.getBackingBlock() ;
+    }
+
+    @Override
+    public BlockMgr getBlockMgr() {
+        return bpTree.getRecordsMgr().getBlockMgr() ;
+    }
+
+    @Override
+    public void reset(Block block) {
+        rBuffPage.reset(block) ;
+        rBuff = rBuffPage.getRecordBuffer() ;
+    }
+
+    int getLink() {
+        return rBuffPage.getLink() ;
+    }
+
+    @Override
+    public boolean isFull() {
+        return (rBuff.size() >= rBuff.maxSize()) ;
+    }
+
+    @Override
+    public boolean hasAnyKeys() {
+        return rBuff.size() > 0 ;
+    }
+
+    @Override
+    public boolean isMinSize() {
+        // 50% packing minimum.
+        // If of max length 5 (i.e. odd), min size is 2. Integer division works.
+        return (rBuff.size() <= rBuff.maxSize() / 2) ;
+    }
+
+    @Override
+    Record internalSearch(AccessPath path, Record rec) {
+        int i = rBuff.find(rec) ;
+        if ( i < 0 )
+            return null ;
+        return rBuff.get(i) ;
+    }
+
+    @Override
+    final public void write() {
+        bprRecordsMgr.write(this) ;
+    }
+
+    @Override
+    final boolean promote() {
+        if ( bprRecordsMgr.isWritable(getId()) )
+            return false ;
+        // reset() will be called if necessary.
+        boolean promoteInPlace = (bpTree == null) ? true : bpTree.state().modifiableRecordsBlock(getId()) ;
+
+        if ( promoteInPlace ) {
+            bprRecordsMgr.promoteInPlace(this) ;
+            // TODO Is this needed?
+            // Is this replicated in BPTreeNode?
+            if ( getBackingBlock().isReadOnly() )
+                bprRecordsMgr.getBlockMgr().promote(getBackingBlock()) ;
+            return false ;
+        } else {
+            Block oldBlock = getBackingBlock() ;
+            boolean b = bprRecordsMgr.promoteDuplicate(this) ;
+            if ( b )
+                bprRecordsMgr.getBlockMgr().release(oldBlock) ;
+            return b ;
+        }
+
+    }
+
+    @Override
+    final public void release() {
+        bprRecordsMgr.release(this) ;
+    }
+
+    @Override
+    final public void free() {
+        bprRecordsMgr.free(this) ;
+    }
+
+    @Override
+    Record internalInsert(AccessPath path, Record record) {
+        // Delay promotion until we know change will happen.
+        int i = rBuff.find(record) ;
+        Record r2 = null ;
+        if ( i < 0 ) {
+            i = decodeIndex(i) ;
+            if ( rBuff.size() >= rBuff.maxSize() )
+                throw new StorageException("RecordBlock.put overflow") ;
+            promotePage(path, this) ;
+            rBuff.add(i, record) ;
+        } else {
+            r2 = rBuff.get(i) ;
+            if ( Record.compareByKeyValue(record, r2) != 0 ) {
+                // Replace : return old
+                promotePage(path, this) ;
+                rBuff.set(i, record) ;
+            } else
+                // No promotion, no write
+                return r2 ;
+        }
+        write() ;
+        return r2 ;
+    }
+
+    @Override
+    Record internalDelete(AccessPath path, Record record) {
+        int i = rBuff.find(record) ;
+        if ( i < 0 )
+            return null ;
+        promotePage(path, this) ;
+        Record r2 = rBuff.get(i) ;
+        rBuff.remove(i) ;
+        write() ;
+        return r2 ;
+    }
+
+    @Override
+    public Record getSplitKey() {
+        int splitIdx = rBuff.size() / 2 - 1 ;
+        Record r = rBuff.get(splitIdx) ;
+        return r ;
+    }
+
+    /**
+     * Split: place old high half in 'other'. Return the new (upper)
+     * BPTreeRecords(BPTreePage).
+     * Split is the high end of the low page.
+     */
+    @Override
+    public BPTreePage split() {
+        BPTreeRecords other = insertNewPage() ;
+        int splitIdx = rBuff.size() / 2 - 1 ;
+        Record r = rBuff.get(splitIdx) ; // Only need key for checking later.
+        int moveLen = rBuff.size() - (splitIdx + 1) ; // Number to move.
+        // Copy high end to new.
+        rBuff.copy(splitIdx + 1, other.getRecordBufferPage().getRecordBuffer(), 0, moveLen) ;
+        rBuff.clear(splitIdx + 1, moveLen) ;
+        rBuff.setSize(splitIdx + 1) ;
+
+        if ( CheckingNode ) {
+            if ( !Record.keyEQ(r, maxRecord()) ) {
+                System.err.println(rBuff) ;
+                System.err.println(other.rBuff) ;
+                error("BPTreeRecords.split: Not returning expected record") ;
+            }
+        }
+        return other ;
+    }
+    
+    private BPTreeRecords insertNewPage() {
+        // MVCC - link can not be maintained. 
+        if ( false /* ! bpTree.isTransaction() */ ) {
+            BPTreeRecords other = create(rBuffPage.getLink()) ;
+            rBuffPage.setLink(other.getId()) ;
+            return other ;
+        } 
+        BPTreeRecords other = create(Page.NO_ID) ;
+        rBuffPage.setLink(Page.NO_ID) ;
+        return other ;
+    }
+
+    private BPTreeRecords create(int linkId) {
+        BPTreeRecords newPage = bprRecordsMgr.create() ;
+        newPage.getRecordBufferPage().setLink(linkId) ;
+        return newPage ;
+    }
+
+    @Override
+    public Record shiftRight(BPTreePage other, Record splitKey) {
+        // Error checking by RecordBuffer
+        BPTreeRecords page = cast(other) ;
+        rBuff.shiftRight(page.rBuff) ;
+        if ( rBuff.size() == 0 )
+            return null ;
+        return rBuff.getHigh() ;
+    }
+
+    @Override
+    public Record shiftLeft(BPTreePage other, Record splitKey) {
+        // Error checking by RecordBuffer
+        BPTreeRecords page = cast(other) ;
+        rBuff.shiftLeft(page.rBuff) ;
+        if ( rBuff.size() == 0 )
+            return null ;
+        return rBuff.getHigh() ;
+    }
+
+    @Override
+    BPTreePage merge(BPTreePage right, Record splitKey) {
+        // Split key ignored - it's for the B+Tree case of pushing down a key
+        // Records blocks have all the key/values in them anyway.
+        return merge(this, cast(right)) ;
+    }
+
+    private static BPTreeRecords merge(BPTreeRecords left, BPTreeRecords right) {
+        // Copy right to top of left.
+        // The other way round needs a shift as well.
+        right.rBuff.copyToTop(left.rBuff) ;
+        // Same as: right.rBuff.copy(0, left.rBuff, left.rBuff.size(),
+        // right.rBuff.size()) ;
+        right.rBuff.clear() ;
+
+        // The right page is released by the caller. left is still in use.
+        // So the test code can poke around in the right block after merge.
+        // left.bpTree.getRecordsMgr().release(left.getId()) ;
+
+        // Fix up the link chain.
+        left.rBuffPage.setLink(right.rBuffPage.getLink()) ;
+        return left ;
+    }
+
+    private static BPTreeRecords cast(BPTreePage page) {
+        try {
+            return (BPTreeRecords)page ;
+        }
+        catch (ClassCastException ex) {
+            error("Wrong type: " + page) ;
+            return null ;
+        }
+    }
+
+    @Override
+    final public Record internalMinRecord(AccessPath path) {
+        return getLowRecord() ;
+    }
+
+    @Override
+    final public Record internalMaxRecord(AccessPath path) {
+        return getHighRecord() ;
+    }
+
+    private static void error(String msg, Object... args) {
+        msg = format(msg, args) ;
+        System.out.println(msg) ;
+        System.out.flush() ;
+        throw new BPTreeException(msg) ;
+    }
+
+    @Override
+    public final Record getLowRecord() {
+        if ( rBuff.size() == 0 )
+            return null ;
+        return rBuff.getLow() ;
+    }
+
+    @Override
+    public final Record getHighRecord() {
+        if ( rBuff.size() == 0 )
+            return null ;
+        return rBuff.getHigh() ;
+    }
+
+    @Override
+    public final int getMaxSize() {
+        return rBuff.maxSize() ;
+    }
+
+    @Override
+    public final int getCount() {
+        return rBuff.size() ;
+    }
+
+    @Override
+    public final void setCount(int count) {
+        rBuff.setSize(count) ;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("BPTreeRecords[id=%d, link=%d]: %s", getId(), getLink(), rBuff.toString()) ;
+    }
+
+    @Override
+    protected String typeMark() {
+        return "Data" ;
+    }
+
+    @Override
+    public final void checkNode() {
+        if ( !CheckingNode )
+            return ;
+        if ( rBuff.size() < 0 || rBuff.size() > rBuff.maxSize() )
+            error("Misized: %s", this) ;
+
+        for ( int i = 1 ; i < getCount() ; i++ ) {
+            Record r1 = rBuff.get(i - 1) ;
+            Record r2 = rBuff.get(i) ;
+            if ( Record.keyGT(r1, r2) )
+                error("Not sorted: %s", this) ;
+        }
+    }
+
+    @Override
+    public final void checkNodeDeep() {
+        checkNode() ;
+    }
+
+    @Override
+    public int getId() {
+        return rBuffPage.getId() ;
+    }
+
+    @Override
+    public String getRefStr() {
+        return String.format("BPTRecord[id=%d]", getBackingBlock().getId()) ;
+    }
+
+    @Override
+    public void output(IndentedWriter out) {
+        out.print(toString()) ;
+    }
+}


Mime
View raw message