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
ConstructorDescriptionCreates 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 TypeMethodDescriptionvoid
clear()
Removes all values from the B-Tree.void
close()
Closes any opened files and release any resources used by this B-Tree.boolean
delete()
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.long
Returns an estimate for the number of values stored in this BTree.long
getValueCountEstimate
(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.void
print
(PrintStream out) byte[]
remove
(byte[] key) Removes the value that matches the specified key from the B-Tree.void
sync()
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:
close
in interfaceAutoCloseable
- Specified by:
close
in 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
-