Module org.apache.jena.dboe.trans.data
Package org.apache.jena.dboe.trans.bplustree

Class BPlusTree

java.lang.Object
org.apache.jena.dboe.transaction.txn.TransactionalComponentLifecycle<org.apache.jena.dboe.trans.bplustree.BptTxnState>
org.apache.jena.dboe.trans.bplustree.BPlusTree
All Implemented Interfaces:
Iterable<org.apache.jena.dboe.base.record.Record>, org.apache.jena.atlas.lib.Closeable, org.apache.jena.atlas.lib.Sync, Index, RangeIndex, TransactionalComponent
public class BPlusTree extends TransactionalComponentLifecycle<org.apache.jena.dboe.trans.bplustree.BptTxnState> implements RangeIndex
B-Tree taken from: 
 Introduction to Algorithms, Second Edition
 Chapter 18: B-Trees
 by Thomas H. Cormen, Charles E. Leiserson,
    Ronald L. Rivest and Clifford Stein
Includes implementation of removal then the B-Tree code converted to a B+Tree, then made MVCC/transactional.

Notes:

  • Stores "records", which are a key and value (the value may be absent).
  • In this B+Tree implementation, the (key,value) pairs are held in RecordBuffer, which wraps a ByteBuffer that only has records in it. BPTreeRecords provides the B+Tree view of a RecordBuffer. All records are in RecordBuffer - the "tree" part is an index for finding the right page. The tree only holds keys, copies from the (key, value) pairs in the RecordBuffers.
  • The version above splits nodes on the way down when full, not when needed where a split can bubble up from below. It means it only ever walks down the tree on insert. Similarly, the delete code ensures a node is suitable before descending.

  • Method Details

    • newRoot

      public void newRoot(BPTreeNode newRoot)

    • getRootId

      public int getRootId()

    • getParams

      public BPlusTreeParams getParams()
      Get the parameters describing this B+Tree

    • getStateManager

      public BPTStateMgr getStateManager()
      Only use for careful manipulation of structures

    • getNodeManager

      public BPTreeNodeMgr getNodeManager()
      Only use for careful manipulation of structures

    • getRecordsMgr

      public BPTreeRecordsMgr getRecordsMgr()
      Only use for careful manipulation of structures

    • getRecordFactory

      public org.apache.jena.dboe.base.record.RecordFactory getRecordFactory()
      Specified by:
      getRecordFactory in interface Index

    • find

      public org.apache.jena.dboe.base.record.Record find(org.apache.jena.dboe.base.record.Record record)
      Specified by:
      find in interface Index

    • contains

      public boolean contains(org.apache.jena.dboe.base.record.Record record)
      Specified by:
      contains in interface Index

    • minKey

      public org.apache.jena.dboe.base.record.Record minKey()
      Specified by:
      minKey in interface RangeIndex

    • maxKey

      public org.apache.jena.dboe.base.record.Record maxKey()
      Specified by:
      maxKey in interface RangeIndex

    • insert

      public boolean insert(org.apache.jena.dboe.base.record.Record record)
      Specified by:
      insert in interface Index

    • insertAndReturnOld

      public org.apache.jena.dboe.base.record.Record insertAndReturnOld(org.apache.jena.dboe.base.record.Record record)
      Add a record into the B+Tree

    • delete

      public boolean delete(org.apache.jena.dboe.base.record.Record record)
      Specified by:
      delete in interface Index

    • deleteAndReturnOld

      public org.apache.jena.dboe.base.record.Record deleteAndReturnOld(org.apache.jena.dboe.base.record.Record record)

    • iterator

      public Iterator<org.apache.jena.dboe.base.record.Record> iterator()
      Specified by:
      iterator in interface Index
      Specified by:
      iterator in interface Iterable<org.apache.jena.dboe.base.record.Record>

    • iterator

      public Iterator<org.apache.jena.dboe.base.record.Record> iterator(org.apache.jena.dboe.base.record.Record fromRec, org.apache.jena.dboe.base.record.Record toRec)
      Specified by:
      iterator in interface RangeIndex

    • distinctByKeyPrefix

      public Iterator<org.apache.jena.dboe.base.record.Record> distinctByKeyPrefix(int keyPrefixLength)

    • iterator

      public <X> Iterator<X> iterator(org.apache.jena.dboe.base.record.Record minRec, org.apache.jena.dboe.base.record.Record maxRec, org.apache.jena.dboe.base.record.RecordMapper<X> mapper)
      Specified by:
      iterator in interface RangeIndex

    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Index

    • clear

      public void clear()
      Specified by:
      clear in interface Index

    • sync

      public void sync()
      Specified by:
      sync in interface org.apache.jena.atlas.lib.Sync

    • close

      public void close()
      Specified by:
      close in interface org.apache.jena.atlas.lib.Closeable
      Specified by:
      close in interface Index

    • size

      public long size()
      Specified by:
      size in interface Index

    • check

      public void check()
      Specified by:
      check in interface Index

    • dump

      public void dump()

    • dump

      public void dump(org.apache.jena.atlas.io.IndentedWriter out)

    • nonTransactional

      public void nonTransactional()

    • startRecovery

      public void startRecovery()
      Specified by:
      startRecovery in interface TransactionalComponent
      Specified by:
      startRecovery in class TransactionalComponentLifecycle<org.apache.jena.dboe.trans.bplustree.BptTxnState>

    • recover

      public void recover(ByteBuffer ref)
      Specified by:
      recover in interface TransactionalComponent
      Specified by:
      recover in class TransactionalComponentLifecycle<org.apache.jena.dboe.trans.bplustree.BptTxnState>

    • finishRecovery

      public void finishRecovery()
      Specified by:
      finishRecovery in interface TransactionalComponent
      Specified by:
      finishRecovery in class TransactionalComponentLifecycle<org.apache.jena.dboe.trans.bplustree.BptTxnState>

    • cleanStart

      public void cleanStart()
      Specified by:
      cleanStart in interface TransactionalComponent