Class SoftBPlusTree<V>

java.lang.Object
org.infinispan.util.BPlusTree<V>
org.infinispan.util.SoftBPlusTree<V>
Type Parameters:
V - value type
public class SoftBPlusTree<V> extends BPlusTree<V>
A BPlusTree subclass that persists each node independently to a SoftBPlusTree.NodeStore and wraps every inner-node child in a SoftBPlusTree.SoftNode.

After each put(byte[], V) or remove(byte[]), only the nodes on the modified path (from the affected leaf up to the root's children) are serialized and written — typically O(height) writes of a few hundred bytes each. Unmodified subtrees keep their existing disk locations. A SoftReference at every inner-node level lets the JVM evict cached subtrees under memory pressure; they are reloaded from disk on demand.

Keys are not stored on disk. On deserialization, keys are loaded from the external data source via the SoftBPlusTree.KeyLoader callback. This matches the old IndexNode disk format exactly.

Disk space is managed internally using a block-aligned free list. Freed blocks are pooled by size and reused for future allocations to avoid unbounded index file growth.

  • Constructor Details

    • SoftBPlusTree

      public SoftBPlusTree(int minNodeSize, int maxNodeSize, SoftBPlusTree.NodeStore store, SoftBPlusTree.ValueSerializer<V> serializer, SoftBPlusTree.KeyLoader<V> keyLoader, short blockAlignment, long initialStoreSize)
      Creates a disk-backed B+ tree with block-aligned free space management.
      Parameters:
      minNodeSize - minimum serialized node size before merging
      maxNodeSize - maximum serialized node size before splitting
      store - backing storage for serialized nodes
      serializer - value serializer/deserializer
      keyLoader - reconstructs keys from values during deserialization
      blockAlignment - disk block alignment in bytes (freed blocks are pooled by aligned size)
      initialStoreSize - starting byte offset for new allocations (typically the header size)

    • SoftBPlusTree

      public SoftBPlusTree(int minNodeSize, int maxNodeSize, SoftBPlusTree.NodeStore store, SoftBPlusTree.ValueSerializer<V> serializer, SoftBPlusTree.KeyLoader<V> keyLoader)
      Creates a disk-backed B+ tree with no block alignment (alignment of 1) and an initial store size of 0.
      See Also:

  • Method Details

    • getStoreSize

      public long getStoreSize()
      Returns the current logical size of the backing store in bytes.

    • setStoreSize

      public void setStoreSize(long size)
      Sets the logical size of the backing store, typically restored from a persisted header.

    • serializeFreeBlocks

      public ByteBuffer serializeFreeBlocks()
      Serializes the free block lists into a ByteBuffer for persistence. The caller should write this alongside the tree root descriptor so that free space can be restored on restart via deserializeFreeBlocks(ByteBuffer).
      Returns:
      a flipped buffer containing the serialized free block state

    • deserializeFreeBlocks

      public void deserializeFreeBlocks(ByteBuffer buf)
      Restores the free block lists from a buffer previously produced by serializeFreeBlocks(). Any existing free block state is replaced.

    • onChildrenReplaced

      protected void onChildrenReplaced(BPlusTree.Node<V>[] oldChildren, int from, int to)
      Overrides:
      onChildrenReplaced in class BPlusTree<V>

    • onValueOverwritten

      protected void onValueOverwritten(Deque<BPlusTree.PathEntry<V>> stack, BPlusTree.LeafNode<V> leaf, int entryIndex)
      Overrides:
      onValueOverwritten in class BPlusTree<V>

    • tryInPlaceLeafUpdate

      protected boolean tryInPlaceLeafUpdate(Deque<BPlusTree.PathEntry<V>> stack, BPlusTree.LeafNode<V> oldLeaf, BPlusTree.LeafNode<V> newLeaf)
      Overrides:
      tryInPlaceLeafUpdate in class BPlusTree<V>

    • get

      public V get(byte[] key)
      Look up a key. Returns the value or null if the key is not present.

      Retries up to MAX_OUTDATED_RETRIES times on SoftBPlusTree.IndexNodeOutdatedException, which can occur when a SoftBPlusTree.SoftNode resolves from disk and the backing data has been concurrently deleted (e.g., by a compactor).

      Overrides:
      get in class BPlusTree<V>

    • put

      public V put(byte[] key, V value)
      Description copied from class: BPlusTree
      Insert or replace a value. Returns the previous value, or null if the key was not present.
      Overrides:
      put in class BPlusTree<V>

    • remove

      public V remove(byte[] key)
      Description copied from class: BPlusTree
      Remove a key. Returns the removed value, or null if the key was not present.
      Overrides:
      remove in class BPlusTree<V>

    • publish

      public <R> io.reactivex.rxjava3.core.Flowable<R> publish(BPlusTree.PublishFunction<V,R> function)
      Returns a Flowable that emits entries in sorted order. The function transforms each entry, returning null to skip. Any exception thrown by the function or during node resolution propagates as a Flowable error; subclasses may override to add retry logic.

      Retries the entire iteration up to MAX_OUTDATED_RETRIES times on SoftBPlusTree.IndexNodeOutdatedException, resuming from the last successfully emitted key. The function may throw SoftBPlusTree.IndexNodeOutdatedException to force a retry for the current entry rather than returning null (which skips the entry without retrying).

      Overrides:
      publish in class BPlusTree<V>

    • publish

      public <R> io.reactivex.rxjava3.core.Flowable<R> publish(SoftBPlusTree.IOPublishFunction<V,R> function, boolean skipOnOutdated)
      Returns a Flowable that emits entries in sorted order with SoftBPlusTree.IndexNodeOutdatedException handling controlled by skipOnOutdated.

      When skipOnOutdated is true, any SoftBPlusTree.IndexNodeOutdatedException thrown by the function is caught and the entry is silently skipped (treated as if the function returned null). Exceptions thrown during node resolution still trigger a full retry. When false, all SoftBPlusTree.IndexNodeOutdatedExceptions trigger a retry.

    • clear

      public void clear()
      Removes all entries, resetting the tree to an empty root leaf.

      Also resets the free block lists, restores the store size to its initial value, and truncates the backing store.

      Overrides:
      clear in class BPlusTree<V>

    • saveTree

      public SoftBPlusTree.NodeSpace saveTree() throws IOException
      Persists the tree to the store. All descendants should already be persisted as SoftNodes (via afterMutation calls during normal operation). This method serializes the root node itself and returns a descriptor that the caller can write into the file header for loadTree(SoftBPlusTree.NodeSpace) to find on restart.

      The free-block state must be persisted separately by the caller via serializeFreeBlocks().

      Returns:
      the root's disk location, or null if the tree is empty
      Throws:
      IOException

    • loadTree

      public void loadTree(SoftBPlusTree.NodeSpace rootSpace) throws IOException
      Reconstructs the tree from a previously persisted root. For an inner root, each child is created as a SoftBPlusTree.SoftNode pointing at its disk location — no child data is loaded until first access.
      Throws:
      IOException