org.apache.directory.mavibot.btree

## Class PersistedBTree<K,V>

- java.lang.Object
- - org.apache.directory.mavibot.btree.PersistedBTree<K,V>

- Type Parameters:
    `K` - The type for the keys
    `V` - The type for the stored values
  All Implemented Interfaces:
    Closeable, AutoCloseable, BTree<K,V>

      public class PersistedBTree<K,V>
      extends Object
      implements Closeable

  The B+Tree MVCC data structure.
  Author:
    Apache Directory Project

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected boolean` | `allowDuplicates` Flag to enable duplicate key support
    `protected Map<Long,org.apache.directory.mavibot.btree.BTreeHeader<K,V>>` | `btreeRevisions` The map of all the used BtreeHeaders
    `protected BTreeTypeEnum` | `btreeType` The BTree type : either in-memory, disk backed or persisted
    `protected org.apache.commons.collections.map.LRUMap` | `cache` The cache associated with this B-tree
    `protected int` | `cacheSize` The cache size, default to 1000 elements
    `protected org.apache.directory.mavibot.btree.BTreeHeader<K,V>` | `currentBtreeHeader` The current Header for a managed BTree
    `protected AtomicLong` | `currentRevision` The current revision
    `static int` | `DEFAULT_CACHE_SIZE` The default number of pages to keep in memory
    `protected ElementSerializer<K>` | `keySerializer` The Key serializer used for this tree.
    `protected String` | `keySerializerFQCN` The FQCN of the Key serializer
    `protected static org.slf4j.Logger` | `LOG` The LoggerFactory used by this class
    `protected static org.slf4j.Logger` | `LOG_PAGES`
    `protected String` | `name` The BTree name
    `protected int` | `pageSize` The number of elements in a page for this B-tree
    `protected long` | `readTimeOut` The read transaction timeout
    `protected ConcurrentLinkedQueue<ReadTransaction<K,V>>` | `readTransactions` The list of read transactions being executed
    `protected Thread` | `readTransactionsThread` The thread responsible for the cleanup of timed out reads
    `protected TransactionManager` | `transactionManager` The TransactionManager used for this BTree
    `protected AtomicBoolean` | `transactionStarted` The current transaction
    `protected ElementSerializer<V>` | `valueSerializer` The Value serializer used for this tree.
    `protected String` | `valueSerializerFQCN` The FQCN of the Value serializer
    `protected int` | `writeBufferSize` The size of the buffer used to write data in disk

    - ### Fields inherited from interface org.apache.directory.mavibot.btree.BTree

      `ALLOW_DUPLICATES, DEFAULT_PAGE_SIZE, DEFAULT_READ_TIMEOUT, DEFAULT_WRITE_BUFFER_SIZE, FORBID_DUPLICATES`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected ReadTransaction<K,V>` | `beginReadTransaction()` Starts a Read Only transaction.
    `protected ReadTransaction<K,V>` | `beginReadTransaction(long revision)` Starts a Read Only transaction.
    `TupleCursor<K,V>` | `browse()` Creates a cursor starting at the beginning of the tree
    `TupleCursor<K,V>` | `browse(long revision)` Creates a cursor starting at the beginning of the tree, for a given revision
    `TupleCursor<K,V>` | `browseFrom(K key)` Creates a cursor starting on the given key
    `TupleCursor<K,V>` | `browseFrom(long revision, K key)` Creates a cursor starting on the given key at the given revision
    `KeyCursor<K>` | `browseKeys()` Creates a cursor starting at the beginning of the tree
    `void` | `close()` Close the BTree, cleaning up all the data structure
    `boolean` | `contains(K key, V value)` Checks if the B-tree contains the given key with the given value.
    `boolean` | `contains(long revision, K key, V value)` Checks if the B-tree contains the given key with the given value for a given revision
    `Tuple<K,V>` | `delete(K key)` Delete the entry which key is given as a parameter.
    `Tuple<K,V>` | `delete(K key, V value)` Delete the value from an entry associated with the given key.
    `void` | `flush()` Flush the latest revision to disk.
    `V` | `get(K key)` Find a value in the tree, given its key.
    `V` | `get(long revision, K key)` Find a value in the tree, given its key, at a specific revision.
    `protected org.apache.directory.mavibot.btree.BTreeHeader<K,V>` | `getBtreeHeader()`
    `protected org.apache.directory.mavibot.btree.BTreeHeader<K,V>` | `getBtreeHeader(long revision)`
    `long` | `getBtreeInfoOffset()`
    `Comparator<K>` | `getKeyComparator()`
    `ElementSerializer<K>` | `getKeySerializer()`
    `String` | `getKeySerializerFQCN()`
    `String` | `getName()`
    `long` | `getNbElems()`
    `int` | `getPageSize()`
    `long` | `getReadTimeOut()`
    `long` | `getRevision()`
    `org.apache.directory.mavibot.btree.Page<K,V>` | `getRootPage()` Get the current rootPage
    `org.apache.directory.mavibot.btree.Page<K,V>` | `getRootPage(long revision)` Get the rootPzge associated to a give revision.
    `BTreeTypeEnum` | `getType()`
    `Comparator<V>` | `getValueComparator()`
    `ValueCursor<V>` | `getValues(K key)`
    `ElementSerializer<V>` | `getValueSerializer()`
    `String` | `getValueSerializerFQCN()`
    `int` | `getWriteBufferSize()`
    `boolean` | `hasKey(K key)` Checks if the given key exists.
    `boolean` | `hasKey(long revision, K key)` Checks if the given key exists for a given revision.
    `void` | `init(BTree<K,V> parentBTree)` Initialize the BTree.
    `V` | `insert(K key, V value)` Insert an entry in the B-tree.
    `boolean` | `isAllowDuplicates()`
    `void` | `setAllowDuplicates(boolean allowDuplicates)`
    `void` | `setBtreeInfoOffset(long btreeInfoOffset)`
    `void` | `setKeySerializer(ElementSerializer<K> keySerializer)`
    `void` | `setName(String name)`
    `void` | `setPageSize(int pageSize)` Set the maximum number of elements we can store in a page.
    `void` | `setReadTimeOut(long readTimeOut)`
    `void` | `setType(BTreeTypeEnum type)`
    `void` | `setValueSerializer(ElementSerializer<V> valueSerializer)`
    `void` | `setWriteBufferSize(int writeBufferSize)`
    `protected void` | `storeRevision(org.apache.directory.mavibot.btree.BTreeHeader<K,V> btreeHeader)` Store the new revision in the map of btrees, increment the current revision
    `protected void` | `storeRevision(org.apache.directory.mavibot.btree.BTreeHeader<K,V> btreeHeader, boolean keepRevisions)` Store the new revision in the map of btrees, increment the current revision
    `String` | `toString()`

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### LOG

          protected static final org.slf4j.Logger LOG

      The LoggerFactory used by this class

    - #### LOG_PAGES

          protected static final org.slf4j.Logger LOG_PAGES

    - #### cache

          protected org.apache.commons.collections.map.LRUMap cache

      The cache associated with this B-tree

    - #### DEFAULT_CACHE_SIZE

          public static final int DEFAULT_CACHE_SIZE

      The default number of pages to keep in memory
      See Also:
        Constant Field Values

    - #### cacheSize

          protected int cacheSize

      The cache size, default to 1000 elements

    - #### readTimeOut

          protected long readTimeOut

      The read transaction timeout

    - #### currentBtreeHeader

          protected org.apache.directory.mavibot.btree.BTreeHeader<K,V> currentBtreeHeader

      The current Header for a managed BTree

    - #### keySerializer

          protected ElementSerializer<K> keySerializer

      The Key serializer used for this tree.

    - #### valueSerializer

          protected ElementSerializer<V> valueSerializer

      The Value serializer used for this tree.

    - #### readTransactions

          protected ConcurrentLinkedQueue<ReadTransaction<K,V>> readTransactions

      The list of read transactions being executed

    - #### writeBufferSize

          protected int writeBufferSize

      The size of the buffer used to write data in disk

    - #### allowDuplicates

          protected boolean allowDuplicates

      Flag to enable duplicate key support

    - #### pageSize

          protected int pageSize

      The number of elements in a page for this B-tree

    - #### name

          protected String name

      The BTree name

    - #### keySerializerFQCN

          protected String keySerializerFQCN

      The FQCN of the Key serializer

    - #### valueSerializerFQCN

          protected String valueSerializerFQCN

      The FQCN of the Value serializer

    - #### readTransactionsThread

          protected Thread readTransactionsThread

      The thread responsible for the cleanup of timed out reads

    - #### btreeType

          protected BTreeTypeEnum btreeType

      The BTree type : either in-memory, disk backed or persisted

    - #### transactionStarted

          protected AtomicBoolean transactionStarted

      The current transaction

    - #### btreeRevisions

          protected Map<Long,org.apache.directory.mavibot.btree.BTreeHeader<K,V>> btreeRevisions

      The map of all the used BtreeHeaders

    - #### currentRevision

          protected AtomicLong currentRevision

      The current revision

    - #### transactionManager

          protected TransactionManager transactionManager

      The TransactionManager used for this BTree

  - ### Method Detail

    - #### init

          public void init(BTree<K,V> parentBTree)

      Initialize the BTree.
      Throws:
        `IOException` - If we get some exception while initializing the BTree

    - #### close

          public void close()
                     throws IOException

      Close the BTree, cleaning up all the data structure
      Specified by:
        `close` in interface `Closeable`
      Specified by:
        `close` in interface `AutoCloseable`
      Specified by:
        `close` in interface `BTree<K,V>`
      Throws:
        `IOException`

    - #### getRootPage

          public org.apache.directory.mavibot.btree.Page<K,V> getRootPage(long revision)
                                                                   throws IOException,
                                                                          KeyNotFoundException

      Get the rootPzge associated to a give revision.
      Specified by:
        `getRootPage` in interface `BTree<K,V>`
      Parameters:
        `revision` - The revision we are looking for
      Returns:
        The rootPage associated to this revision
      Throws:
        `IOException` - If we had an issue while accessing the underlying file
        `KeyNotFoundException` - If the revision does not exist for this Btree

    - #### getRootPage

          public org.apache.directory.mavibot.btree.Page<K,V> getRootPage()

      Get the current rootPage
      Specified by:
        `getRootPage` in interface `BTree<K,V>`
      Returns:
        The rootPage

    - #### getBtreeInfoOffset

          public long getBtreeInfoOffset()

      Returns:
        the btreeInfoOffset

    - #### setBtreeInfoOffset

          public void setBtreeInfoOffset(long btreeInfoOffset)

      Parameters:
        `btreeInfoOffset` - the btreeInfoOffset to set

    - #### beginReadTransaction

          protected ReadTransaction<K,V> beginReadTransaction()

      Starts a Read Only transaction. If the transaction is not closed, it will be automatically closed after the timeout
      Returns:
        The created transaction

    - #### beginReadTransaction

          protected ReadTransaction<K,V> beginReadTransaction(long revision)

      Starts a Read Only transaction. If the transaction is not closed, it will be automatically closed after the timeout
      Returns:
        The created transaction

    - #### toString

          public String toString()

      Overrides:
        `toString` in class `Object`
      See Also:
        `Object.toString()`

    - #### browse

          public TupleCursor<K,V> browse()
                                  throws IOException,
                                         KeyNotFoundException

      Creates a cursor starting at the beginning of the tree
      Specified by:
        `browse` in interface `BTree<K,V>`
      Returns:
        A cursor on the B-tree
      Throws:
        `IOException`
        `KeyNotFoundException`

    - #### browse

          public TupleCursor<K,V> browse(long revision)
                                  throws IOException,
                                         KeyNotFoundException

      Creates a cursor starting at the beginning of the tree, for a given revision
      Specified by:
        `browse` in interface `BTree<K,V>`
      Parameters:
        `revision` - The revision we would like to browse
      Returns:
        A cursor on the B-tree
      Throws:
        `IOException` - If we had an issue while fetching data from the disk
        `KeyNotFoundException` - If the key is not found in the B-tree

    - #### browseFrom

          public TupleCursor<K,V> browseFrom(K key)
                                      throws IOException

      Creates a cursor starting on the given key
      Specified by:
        `browseFrom` in interface `BTree<K,V>`
      Parameters:
        `key` - The key which is the starting point. If the key is not found, then the cursor will always return null.
      Returns:
        A cursor on the B-tree
      Throws:
        `IOException`

    - #### browseFrom

          public TupleCursor<K,V> browseFrom(long revision,
                                    K key)
                                      throws IOException,
                                             KeyNotFoundException

      Creates a cursor starting on the given key at the given revision
      Specified by:
        `browseFrom` in interface `BTree<K,V>`
        `key` - The key which is the starting point. If the key is not found, then the cursor will always return null.
      Returns:
        A cursor on the B-tree
      Throws:
        `IOException` - If wxe had an issue reading the B-tree from disk
        `KeyNotFoundException` - If we can't find a rootPage for this revision

    - #### contains

          public boolean contains(K key,
                         V value)
                           throws IOException

      Checks if the B-tree contains the given key with the given value.
      Specified by:
        `contains` in interface `BTree<K,V>`
      Parameters:
        `key` - The key we are looking for
        `value` - The value associated with the given key
      Returns:
        true if the key and value are associated with each other, false otherwise
      Throws:
        `IOException`

    - #### contains

          public boolean contains(long revision,
                         K key,
                         V value)
                           throws IOException,
                                  KeyNotFoundException

      Checks if the B-tree contains the given key with the given value for a given revision
      Specified by:
        `contains` in interface `BTree<K,V>`
      Parameters:
        `revision` - The revision we would like to browse
        `key` - The key we are looking for
        `value` - The value associated with the given key
      Returns:
        true if the key and value are associated with each other, false otherwise
      Throws:
        `KeyNotFoundException` - If the key is not found in the B-tree
        `IOException`

    - #### delete

          public Tuple<K,V> delete(K key)
                            throws IOException

      Delete the entry which key is given as a parameter. If the entry exists, it will be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
      Specified by:
        `delete` in interface `BTree<K,V>`
      Parameters:
        `key` - The key for the entry we try to remove
      Returns:
        A Tuple containing the removed entry, or null if it's not found.
      Throws:
        `IOException`

    - #### delete

          public Tuple<K,V> delete(K key,
                          V value)
                            throws IOException

      Delete the value from an entry associated with the given key. If the value If the value is present, it will be deleted first, later if there are no other values associated with this key(which can happen when duplicates are enabled), we will remove the key from the tree.
      Specified by:
        `delete` in interface `BTree<K,V>`
      Parameters:
        `key` - The key for the entry we try to remove
        `value` - The value to delete (can be null)
      Returns:
        A Tuple containing the removed entry, or null if it's not found.
      Throws:
        `IOException`

    - #### insert

          public V insert(K key,
                 V value)
                   throws IOException

      Insert an entry in the B-tree.

      We will replace the value if the provided key already exists in the B-tree.

      Specified by:
        `insert` in interface `BTree<K,V>`
      Parameters:
        `key` - Inserted key
        `value` - Inserted value
      Returns:
        Existing value, if any.
      Throws:
        `IOException` - TODO

    - #### flush

          public void flush()
                     throws IOException

      Flush the latest revision to disk. We will replace the current file by the new one, as we flush in a temporary file.
      Specified by:
        `flush` in interface `BTree<K,V>`
      Throws:
        `IOException`

    - #### get

          public V get(K key)
                throws IOException,
                       KeyNotFoundException

      Find a value in the tree, given its key. If the key is not found, it will throw a KeyNotFoundException.
      Note that we can get a null value stored, or many values.
      Specified by:
        `get` in interface `BTree<K,V>`
      Parameters:
        `key` - The key we are looking at
      Returns:
        The found value, or null if the key is not present in the tree
      Throws:
        `IOException` - TODO
        `KeyNotFoundException` - If the key is not found in the B-tree

    - #### get

          public V get(long revision,
              K key)
                throws IOException,
                       KeyNotFoundException

      Find a value in the tree, given its key, at a specific revision. If the key is not found, it will throw a KeyNotFoundException.
      Note that we can get a null value stored, or many values.
      Specified by:
        `get` in interface `BTree<K,V>`
      Parameters:
        `revision` - The revision for which we want to find a key
        `key` - The key we are looking at
      Returns:
        The found value, or null if the key is not present in the tree
      Throws:
        `IOException` - If there was an issue while fetching data from the disk
        `KeyNotFoundException` - If the key is not found in the B-tree

    - #### getValues

          public ValueCursor<V> getValues(K key)
                                   throws IOException,
                                          KeyNotFoundException

      Specified by:
        `getValues` in interface `BTree<K,V>`
      Throws:
        `IOException`
        `KeyNotFoundException`
      See Also:
        `Page.getValues(Object)`

    - #### hasKey

          public boolean hasKey(K key)
                         throws IOException,
                                KeyNotFoundException

      Checks if the given key exists.
      Specified by:
        `hasKey` in interface `BTree<K,V>`
      Parameters:
        `key` - The key we are looking at
      Returns:
        true if the key is present, false otherwise
      Throws:
        `IOException` - If we have an error while trying to access the page
        `KeyNotFoundException` - If the key is not found in the B-tree

    - #### hasKey

          public boolean hasKey(long revision,
                       K key)
                         throws IOException,
                                KeyNotFoundException

      Checks if the given key exists for a given revision.
      Specified by:
        `hasKey` in interface `BTree<K,V>`
      Parameters:
        `revision` - The revision for which we want to find a key
        `key` - The key we are looking at
      Returns:
        true if the key is present, false otherwise
      Throws:
        `IOException` - If we have an error while trying to access the page
        `KeyNotFoundException` - If the key is not found in the B-tree

    - #### getKeySerializer

          public ElementSerializer<K> getKeySerializer()

      Specified by:
        `getKeySerializer` in interface `BTree<K,V>`
      Returns:
        the keySerializer

    - #### setKeySerializer

          public void setKeySerializer(ElementSerializer<K> keySerializer)

      Specified by:
        `setKeySerializer` in interface `BTree<K,V>`
      Parameters:
        `keySerializer` - the Key serializer to set

    - #### getKeySerializerFQCN

          public String getKeySerializerFQCN()

      Specified by:
        `getKeySerializerFQCN` in interface `BTree<K,V>`
      Returns:
        the keySerializer FQCN

    - #### getValueSerializer

          public ElementSerializer<V> getValueSerializer()

      Specified by:
        `getValueSerializer` in interface `BTree<K,V>`
      Returns:
        the valueSerializer

    - #### setValueSerializer

          public void setValueSerializer(ElementSerializer<V> valueSerializer)

      Specified by:
        `setValueSerializer` in interface `BTree<K,V>`
      Parameters:
        `valueSerializer` - the Value serializer to set

    - #### getValueSerializerFQCN

          public String getValueSerializerFQCN()

      Specified by:
        `getValueSerializerFQCN` in interface `BTree<K,V>`
      Returns:
        the valueSerializer FQCN

    - #### getRevision

          public long getRevision()

      Specified by:
        `getRevision` in interface `BTree<K,V>`
      Returns:
        The current B-tree revision

    - #### storeRevision

          protected void storeRevision(org.apache.directory.mavibot.btree.BTreeHeader<K,V> btreeHeader,
                           boolean keepRevisions)

      Store the new revision in the map of btrees, increment the current revision

    - #### storeRevision

          protected void storeRevision(org.apache.directory.mavibot.btree.BTreeHeader<K,V> btreeHeader)

      Store the new revision in the map of btrees, increment the current revision

    - #### getReadTimeOut

          public long getReadTimeOut()

      Specified by:
        `getReadTimeOut` in interface `BTree<K,V>`
      Returns:
        the readTimeOut

    - #### setReadTimeOut

          public void setReadTimeOut(long readTimeOut)

      Specified by:
        `setReadTimeOut` in interface `BTree<K,V>`
      Parameters:
        `readTimeOut` - the readTimeOut to set

    - #### getNbElems

          public long getNbElems()

      Specified by:
        `getNbElems` in interface `BTree<K,V>`
      Returns:
        The current number of elements in the B-tree

    - #### getPageSize

          public int getPageSize()

      Specified by:
        `getPageSize` in interface `BTree<K,V>`
      Returns:
        the number of elements per page

    - #### setPageSize

          public void setPageSize(int pageSize)

      Set the maximum number of elements we can store in a page. This must be a number greater than 1, and a power of 2. The default page size is 16.
      If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.
      If the provided size is not a power of 2, we will select the closest power of 2 higher than the given number
      Specified by:
        `setPageSize` in interface `BTree<K,V>`
      Parameters:
        `pageSize` - The requested page size

    - #### getName

          public String getName()

      Specified by:
        `getName` in interface `BTree<K,V>`
      Returns:
        the name

    - #### setName

          public void setName(String name)

      Specified by:
        `setName` in interface `BTree<K,V>`
      Parameters:
        `name` - the name to set

    - #### getKeyComparator

          public Comparator<K> getKeyComparator()

      Specified by:
        `getKeyComparator` in interface `BTree<K,V>`
      Returns:
        the key comparator

    - #### getValueComparator

          public Comparator<V> getValueComparator()

      Specified by:
        `getValueComparator` in interface `BTree<K,V>`
      Returns:
        the value comparator

    - #### getWriteBufferSize

          public int getWriteBufferSize()

      Specified by:
        `getWriteBufferSize` in interface `BTree<K,V>`
      Returns:
        the writeBufferSize

    - #### setWriteBufferSize

          public void setWriteBufferSize(int writeBufferSize)

      Specified by:
        `setWriteBufferSize` in interface `BTree<K,V>`
      Parameters:
        `writeBufferSize` - the writeBufferSize to set

    - #### isAllowDuplicates

          public boolean isAllowDuplicates()

      Specified by:
        `isAllowDuplicates` in interface `BTree<K,V>`
      Returns:
        true if this B-tree allow duplicate values

    - #### setAllowDuplicates

          public void setAllowDuplicates(boolean allowDuplicates)

      Specified by:
        `setAllowDuplicates` in interface `BTree<K,V>`
      Parameters:
        `allowDuplicates` - True if the B-tree will allow duplicate values

    - #### getType

          public BTreeTypeEnum getType()

      Specified by:
        `getType` in interface `BTree<K,V>`
      Returns:
        the type

    - #### setType

          public void setType(BTreeTypeEnum type)

      Parameters:
        `type` - the type to set

    - #### getBtreeHeader

          protected org.apache.directory.mavibot.btree.BTreeHeader<K,V> getBtreeHeader()

      Returns:
        The current BtreeHeader

    - #### getBtreeHeader

          protected org.apache.directory.mavibot.btree.BTreeHeader<K,V> getBtreeHeader(long revision)

      Returns:
        The current BtreeHeader

    - #### browseKeys

          public KeyCursor<K> browseKeys()
                                  throws IOException,
                                         KeyNotFoundException

      Creates a cursor starting at the beginning of the tree
      Specified by:
        `browseKeys` in interface `BTree<K,V>`
      Returns:
        A cursor on the B-tree keys
      Throws:
        `IOException`
        `KeyNotFoundException`

Copyright © 2012–2015 Apache Mavibot Project Parent. All rights reserved.