Class BTree

java.lang.Object
org.eclipse.rdf4j.sail.nativerdf.btree.BTree
All Implemented Interfaces:
Closeable, AutoCloseable
public class BTree extends Object implements Closeable
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
    • .
The first reference was used to implement this class.

Author:
Arjohn Kampman, Enrico Minack

  • Constructor Summary

    Constructors
    Constructor
    Description
    BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize)
    Creates a new BTree that uses an instance of DefaultRecordComparator to compare values.
    BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize, boolean forceSync)
    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 Type
    Method
    Description
    void
    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.
    File
    getFile()
    Gets the file that this BTree operates on.
    long
    getValueCountEstimate()
    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.
    RecordIterator
    iterateAll()
    Returns an iterator that iterates over all values in this B-Tree.
    RecordIterator
    iterateRange(byte[] minValue, byte[] maxValue)
    Returns an iterator that iterates over all values between minValue and maxValue, inclusive.
    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.
    RecordIterator
    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.
    String
    toString()
     

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • BTree

      public BTree(File dataDir, String filenamePrefix, int blockSize, int valueSize) 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.
      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 calling FileChannel.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 calling FileChannel.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

      public File getFile()
      Gets the file that this BTree operates on.

    • delete

      public boolean delete() throws IOException
      Closes the BTree and then deletes its data files.
      Returns:
      true if the operation was successful.
      Throws:
      IOException

    • close

      public void close() throws IOException
      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 interface AutoCloseable
      Specified by:
      close in interface Closeable
      Throws:
      IOException

    • sync

      public void sync() throws IOException
      Writes any changes that are cached in memory to disk.
      Throws:
      IOException

    • get

      public byte[] get(byte[] key) throws IOException
      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

      public RecordIterator iterateAll()
      Returns an iterator that iterates over all values in this B-Tree.

    • iterateRange

      public RecordIterator iterateRange(byte[] minValue, byte[] maxValue)
      Returns an iterator that iterates over all values between minValue and maxValue, inclusive.

    • iterateValues

      public RecordIterator 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.

    • 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

      public long getValueCountEstimate() throws IOException
      Returns an estimate for the number of values stored in this BTree.
      Throws:
      IOException

    • getValueCountEstimate

      public long getValueCountEstimate(byte[] minValue, byte[] maxValue) throws IOException
      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

      public byte[] insert(byte[] value) throws IOException
      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

      public byte[] remove(byte[] key) throws IOException
      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

      public void clear() throws IOException
      Removes all values from the B-Tree.
      Throws:
      IOException - If an I/O error occurred.

    • print

      public void print(PrintStream out) throws IOException
      Throws:
      IOException

    • toString

      public String toString()
      Overrides:
      toString in class Object