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.

Nested Class Summary

Nested classes/interfaces inherited from class org.apache.jena.dboe.transaction.txn.TransactionalComponentLifecycle

TransactionalComponentLifecycle.ComponentState<X>

Method Summary

Modifier and Type	Method and Description
void	check()
void	cleanStart()
void	clear()
void	close()
boolean	contains(org.apache.jena.dboe.base.record.Record record)
boolean	delete(org.apache.jena.dboe.base.record.Record record)
org.apache.jena.dboe.base.record.Record	deleteAndReturnOld(org.apache.jena.dboe.base.record.Record record)
void	dump()
void	dump(org.apache.jena.atlas.io.IndentedWriter out)
org.apache.jena.dboe.base.record.Record	find(org.apache.jena.dboe.base.record.Record record)
void	finishRecovery()
BPTreeNodeMgr	getNodeManager() Only use for careful manipulation of structures
BPlusTreeParams	getParams() Get the parameters describing this B+Tree
org.apache.jena.dboe.base.record.RecordFactory	getRecordFactory()
BPTreeRecordsMgr	getRecordsMgr() Only use for careful manipulation of structures
int	getRootId()
BPTStateMgr	getStateManager() Only use for careful manipulation of structures
boolean	insert(org.apache.jena.dboe.base.record.Record record)
org.apache.jena.dboe.base.record.Record	insertAndReturnOld(org.apache.jena.dboe.base.record.Record record) Add a record into the B+Tree
boolean	isEmpty()
Iterator<org.apache.jena.dboe.base.record.Record>	iterator()
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)
<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)
org.apache.jena.dboe.base.record.Record	maxKey()
org.apache.jena.dboe.base.record.Record	minKey()
void	newRoot(BPTreeNode newRoot)
void	nonTransactional()
void	recover(ByteBuffer ref)
long	size()
void	startRecovery()
void	sync()

Methods inherited from class org.apache.jena.dboe.transaction.txn.TransactionalComponentLifecycle

abort, attach, begin, commit, commitEnd, commitPrepare, complete, detach, getComponentId, getComponentState, promote, setComponentState, shutdown

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.jena.dboe.index.Index

bulkChanges

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Method Detail

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 Iterable<org.apache.jena.dboe.base.record.Record>

Specified by:

iterator in interface Index

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

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