jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a...@apache.org
Subject [32/65] [abbrv] jena git commit: JENA-1397: Rename java packages
Date Tue, 03 Oct 2017 19:34:18 GMT
http://git-wip-us.apache.org/repos/asf/jena/blob/3d456654/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNode.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNode.java b/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNode.java
deleted file mode 100644
index 0eb1c22..0000000
--- a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNode.java
+++ /dev/null
@@ -1,1508 +0,0 @@
-/*
- * 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.seaborne.dboe.trans.bplustree;
-
-import static org.seaborne.dboe.base.record.Record.keyGT ;
-import static org.seaborne.dboe.base.record.Record.keyLT ;
-import static org.seaborne.dboe.base.record.Record.keyNE ;
-import static org.seaborne.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.seaborne.dboe.base.block.Block ;
-import org.seaborne.dboe.base.block.BlockMgr ;
-import org.seaborne.dboe.base.buffer.PtrBuffer ;
-import org.seaborne.dboe.base.buffer.RecordBuffer ;
-import org.seaborne.dboe.base.page.PageBlockMgr ;
-import org.seaborne.dboe.base.record.Record ;
-import org.seaborne.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/seaborne/dboe/trans/bplustree/BPTreeNodeMgr.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNodeMgr.java b/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNodeMgr.java
deleted file mode 100644
index 7cdf875..0000000
--- a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeNodeMgr.java
+++ /dev/null
@@ -1,229 +0,0 @@
-/*
- * 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.seaborne.dboe.trans.bplustree;
-
-import static org.seaborne.dboe.base.block.BlockType.BPTREE_BRANCH ;
-import static org.seaborne.dboe.base.block.BlockType.BPTREE_LEAF ;
-import static org.seaborne.dboe.base.block.BlockType.RECORD_BLOCK ;
-
-import java.nio.ByteBuffer ;
-
-import org.seaborne.dboe.base.block.Block ;
-import org.seaborne.dboe.base.block.BlockMgr ;
-import org.seaborne.dboe.base.block.BlockType ;
-import org.seaborne.dboe.base.buffer.PtrBuffer ;
-import org.seaborne.dboe.base.buffer.RecordBuffer ;
-import org.seaborne.dboe.base.page.BlockConverter ;
-import org.seaborne.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/seaborne/dboe/trans/bplustree/BPTreePage.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreePage.java b/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreePage.java
deleted file mode 100644
index 1b682d2..0000000
--- a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreePage.java
+++ /dev/null
@@ -1,136 +0,0 @@
-/*
- * 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.seaborne.dboe.trans.bplustree;
-
-import org.seaborne.dboe.base.block.BlockMgr ;
-import org.seaborne.dboe.base.page.Page ;
-import org.seaborne.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/seaborne/dboe/trans/bplustree/BPTreeRangeIterator.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRangeIterator.java b/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRangeIterator.java
deleted file mode 100644
index 4ed5345..0000000
--- a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRangeIterator.java
+++ /dev/null
@@ -1,153 +0,0 @@
-/*
- * 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.seaborne.dboe.trans.bplustree;
-
-import java.util.* ;
-
-import org.apache.jena.atlas.iterator.Iter ;
-import org.apache.jena.atlas.lib.InternalErrorException ;
-import org.seaborne.dboe.base.record.Record ;
-import org.seaborne.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/seaborne/dboe/trans/bplustree/BPTreeRecords.java
----------------------------------------------------------------------
diff --git a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRecords.java b/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRecords.java
deleted file mode 100644
index 37c5320..0000000
--- a/jena-db/jena-dboe-trans-data/src/main/java/org/seaborne/dboe/trans/bplustree/BPTreeRecords.java
+++ /dev/null
@@ -1,389 +0,0 @@
-/*
- * 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.seaborne.dboe.trans.bplustree ;
-
-import static java.lang.String.format ;
-import static org.apache.jena.atlas.lib.Alg.decodeIndex ;
-import static org.seaborne.dboe.trans.bplustree.BPT.CheckingNode ;
-import static org.seaborne.dboe.trans.bplustree.BPT.promotePage ;
-
-import org.apache.jena.atlas.io.IndentedWriter ;
-import org.seaborne.dboe.base.StorageException ;
-import org.seaborne.dboe.base.block.Block ;
-import org.seaborne.dboe.base.block.BlockMgr ;
-import org.seaborne.dboe.base.buffer.RecordBuffer ;
-import org.seaborne.dboe.base.page.Page ;
-import org.seaborne.dboe.base.record.Record ;
-import org.seaborne.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