Class BTree
java.lang.Object
org.eclipse.rdf4j.sail.nativerdf.btree.BTree
- All Implemented Interfaces:
Closeable,AutoCloseable
Implementation of an on-disk B-Tree using the java.nio classes that are available in JDK 1.4 and newer.
Documentation about B-Trees can be found on-line at the following URLs:
- http://cis.stvincent.edu/swd/btree/btree.html ,
- http://bluerwhite.org/btree/ , and
- http://semaphorecorp.com/btp/algo.html .
- Author:
- Arjohn Kampman, Enrico Minack
-
Constructor Summary
ConstructorsConstructorDescriptionCreates a new BTree that uses an instance of DefaultRecordComparator to compare values.Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, RecordComparator comparator) Creates a new BTree that uses the supplied RecordComparator to compare the values that are or will be stored in the B-Tree.BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, RecordComparator comparator, boolean forceSync) Creates a new BTree that uses the supplied RecordComparator to compare the values that are or will be stored in the B-Tree. -
Method Summary
Modifier and TypeMethodDescriptionvoidclear()Removes all values from the B-Tree.voidclose()Closes any opened files and release any resources used by this B-Tree.booleandelete()Closes the BTree and then deletes its data files.byte[]get(byte[] key) Gets the value that matches the specified key.getFile()Gets the file that this BTree operates on.longReturns an estimate for the number of values stored in this BTree.longgetValueCountEstimate(byte[] minValue, byte[] maxValue) Gives an estimate of the number of values between minValue and maxValue.byte[]insert(byte[] value) Inserts the supplied value into the B-Tree.Returns an iterator that iterates over all values in this B-Tree.iterateRange(byte[] minValue, byte[] maxValue) Returns an iterator that iterates over all values between minValue and maxValue, inclusive.iterateRangedValues(byte[] searchKey, byte[] searchMask, byte[] minValue, byte[] maxValue) Returns an iterator that iterates over all values between minValue and maxValue (inclusive) and returns the values that match the supplied searchKey after searchMask has been applied to the value.iterateValues(byte[] searchKey, byte[] searchMask) Returns an iterator that iterates over all values and returns the values that match the supplied searchKey after searchMask has been applied to the value.voidprint(PrintStream out) byte[]remove(byte[] key) Removes the value that matches the specified key from the B-Tree.voidsync()Writes any changes that are cached in memory to disk.toString()
-
Constructor Details
-
BTree
Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.- Parameters:
dataDir- The directory for the BTree data.filenamePrefix- The prefix for all files used by this BTree.blockSize- The size (in bytes) of a file block for a single node. Ideally, the size specified is the size of a block in the used file system.valueSize- The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.- Throws:
IOException- In case the initialization of the B-Tree file failed.- See Also:
-
BTree
public BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, boolean forceSync) throws IOException Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.- Parameters:
dataDir- The directory for the BTree data.filenamePrefix- The prefix for all files used by this BTree.blockSize- The size (in bytes) of a file block for a single node. Ideally, the size specified is the size of a block in the used file system.valueSize- The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.forceSync- Flag indicating whether updates should be synced to disk forcefully by callingFileChannel.force(boolean). This may have a severe impact on write performance.- Throws:
IOException- In case the initialization of the B-Tree file failed.- See Also:
-
BTree
public BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, RecordComparator comparator) throws IOException Creates a new BTree that uses the supplied RecordComparator to compare the values that are or will be stored in the B-Tree.- Parameters:
dataDir- The directory for the BTree data.filenamePrefix- The prefix for all files used by this BTree.blockSize- The size (in bytes) of a file block for a single node. Ideally, the size specified is the size of a block in the used file system.valueSize- The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.comparator- The RecordComparator to use for determining whether one value is smaller, larger or equal to another.- Throws:
IOException- In case the initialization of the B-Tree file failed.
-
BTree
public BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, RecordComparator comparator, boolean forceSync) throws IOException Creates a new BTree that uses the supplied RecordComparator to compare the values that are or will be stored in the B-Tree.- Parameters:
dataDir- The directory for the BTree data.filenamePrefix- The prefix for all files used by this BTree.blockSize- The size (in bytes) of a file block for a single node. Ideally, the size specified is the size of a block in the used file system.valueSize- The size (in bytes) of the fixed-length values that are or will be stored in the B-Tree.comparator- The RecordComparator to use for determining whether one value is smaller, larger or equal to another.forceSync- Flag indicating whether updates should be synced to disk forcefully by callingFileChannel.force(boolean). This may have a severe impact on write performance.- Throws:
IOException- In case the initialization of the B-Tree file failed.
-
-
Method Details
-
getFile
Gets the file that this BTree operates on. -
delete
Closes the BTree and then deletes its data files.- Returns:
- true if the operation was successful.
- Throws:
IOException
-
close
Closes any opened files and release any resources used by this B-Tree. Any pending changes will be synchronized to disk before closing. Once the B-Tree has been closed, it can no longer be used.- Specified by:
closein interfaceAutoCloseable- Specified by:
closein interfaceCloseable- Throws:
IOException
-
sync
Writes any changes that are cached in memory to disk.- Throws:
IOException
-
get
Gets the value that matches the specified key.- Parameters:
key- A value that is equal to the value that should be retrieved, at least as far as the RecordComparator of this BTree is concerned.- Returns:
- The value matching the key, or null if no such value could be found.
- Throws:
IOException
-
iterateAll
Returns an iterator that iterates over all values in this B-Tree. -
iterateRange
Returns an iterator that iterates over all values between minValue and maxValue, inclusive. -
iterateValues
Returns an iterator that iterates over all values and returns the values that match the supplied searchKey after searchMask has been applied to the value. -
iterateRangedValues
public RecordIterator iterateRangedValues(byte[] searchKey, byte[] searchMask, byte[] minValue, byte[] maxValue) Returns an iterator that iterates over all values between minValue and maxValue (inclusive) and returns the values that match the supplied searchKey after searchMask has been applied to the value. -
getValueCountEstimate
Returns an estimate for the number of values stored in this BTree.- Throws:
IOException
-
getValueCountEstimate
Gives an estimate of the number of values between minValue and maxValue.- Parameters:
minValue- the lower bound of the range.maxValue- the upper bound of the range,- Returns:
- an estimate of the number of values in the specified range.
- Throws:
IOException
-
insert
Inserts the supplied value into the B-Tree. In case an equal value is already present in the B-Tree this value is overwritten with the new value and the old value is returned by this method.- Parameters:
value- The value to insert into the B-Tree.- Returns:
- The old value that was replaced, if any.
- Throws:
IOException- If an I/O error occurred.
-
remove
Removes the value that matches the specified key from the B-Tree.- Parameters:
key- A key that matches the value that should be removed from the B-Tree.- Returns:
- The value that was removed from the B-Tree, or null if no matching value was found.
- Throws:
IOException- If an I/O error occurred.
-
clear
Removes all values from the B-Tree.- Throws:
IOException- If an I/O error occurred.
-
print
- Throws:
IOException
-
toString
-