Class BPlusTree<V>

java.lang.Object
org.infinispan.util.BPlusTree<V>
Type Parameters:
V - value type
Direct Known Subclasses:
SoftBPlusTree
public class BPlusTree<V> extends Object
An in-memory B+ tree with prefix-compressed byte[] keys and generic values.

Concurrent reads are safe against single-threaded writes: node fields are final for safe publication and the root reference is volatile. Callers must ensure at most one writer at a time. When a mutation creates new nodes that propagate up to the root, the volatile write to root provides a happens-before edge and readers see a fully consistent snapshot. However, two mutations are performed in-place without updating the root: value overwrites (existing key gets a new value) and child replacements when the new node fits within maxNodeSize. In these cases there is no volatile write, so readers on other threads may not see the update immediately on weakly-ordered architectures. This is acceptable for the SIFS index use case where the cache layer above handles consistency. A stricter use case would require VarHandle release/acquire semantics on the array elements, or always path-copying up to root.

Subclasses may extend BPlusTree.Node to add custom behavior (e.g. soft-referenced disk-backed nodes). Override BPlusTree.Node.resolve() to transparently unwrap such wrappers during traversal.

  • Field Details

    • RESERVED_SPACE

      public static final int RESERVED_SPACE
      The minimum node size that guarantees room for the header plus at least two child references. Callers should ensure maxNodeSize >= RESERVED_SPACE.

    • minNodeSize

      protected final int minNodeSize

    • maxNodeSize

      protected final int maxNodeSize

  • Constructor Details

    • BPlusTree

      public BPlusTree(int minNodeSize, int maxNodeSize)
      Creates an empty B+ tree.
      Parameters:
      minNodeSize - minimum serialized node size in bytes before a merge is attempted
      maxNodeSize - maximum serialized node size in bytes before a split is triggered

  • Method Details

    • size

      public int size()
      Returns the number of entries in the tree.

    • onChildrenReplaced

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

    • onValueOverwritten

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

    • tryInPlaceLeafUpdate

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

    • get

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

    • put

      public V put(byte[] key, V value)
      Insert or replace a value. Returns the previous value, or null if the key was not present.

    • remove

      public V remove(byte[] key)
      Remove a key. Returns the removed value, or null if the key was not present.

    • clear

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

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