Package org.eclipse.rdf4j.sail.nativerdf.btree

Class 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

      All Methods Instance Methods Concrete Methods 
      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.

    • Constructor Detail

      • 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:
        DefaultRecordComparator

      • 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:
        DefaultRecordComparator

      • 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 Detail

      • 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.