org.mapdb / BTreeMap


class BTreeMap<K, V> : Verifiable, Closeable, Serializable, ConcurrencyAware, ConcurrentNavigableMap<K, V>, ConcurrentNavigableMapExtra<K, V>

A scalable concurrent {@link ConcurrentNavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time.

Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw {@link ConcurrentModificationException}, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

By default BTreeMap does not track its size and {@code size()} traverses collection to count its entries. There is option to enable counter, in that case {@code size()} returns instantly

Additionally, the bulk operations putAll, equals, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements. NOTE: there is an optional

This class and its views and iterators implement all of the optional methods of the {@link Map} and {@link Iterator} interfaces. Like most other concurrent collections, this class does not permit the use of null keys or values because some null return values cannot be reliably distinguished from the absence of

Theoretical design of BTreeMap is based on 1986 paper Concurrent operations on B∗-trees with overtaking written by Yehoshua Sagiv. More practical aspects of BTreeMap implementation are based on demo application from Thomas Dinsdale-Young. Also more work from Thomas: A Simple Abstraction for Complex Concurrent Indexes

B-Linked-Tree used here does not require locking for read. Updates and inserts locks only one, two or three nodes.

This B-Linked-Tree structure does not support removal well, entry deletion does not collapse tree nodes. Massive deletion causes empty nodes and performance lost. There is workaround in form of compaction process, but it is not implemented yet.

Jan Kotek

some parts by Doug Lea and JSR-166 group


BTreeBoundIterator abstract class BTreeBoundIterator<K, V>
BTreeIterator abstract class BTreeIterator<K, V>
DescendingBoundIterator abstract class DescendingBoundIterator<K, V>
DescendingIterator abstract class DescendingIterator<K, V>


<init> BTreeMap(keySerializer: GroupSerializer<K>, valueSerializer: GroupSerializer<V>, rootRecidRecid: Long, store: Store, valueInline: Boolean, maxNodeSize: Int, comparator: Comparator<K>, isThreadSafe: Boolean, counterRecid: Long, hasValues: Boolean, modificationListeners: Array<MapModificationListener<K, V>>?)

A scalable concurrent {@link ConcurrentNavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time.


comparator val comparator: Comparator<K>
counterRecid val counterRecid: Long
entries val entries: MutableSet<MutableEntry<K, V?>>
hasValues val hasValues: Boolean
isThreadSafe val isThreadSafe: Boolean

returns true if this is configured to be thread safe

keySerializer val keySerializer: GroupSerializer<K>
keys val keys: NavigableSet<K?>
leftEdges val leftEdges: <ERROR CLASS>

recids of left-most nodes in tree

locks val locks: ConcurrentHashMap<Long, Long>
maxNodeSize val maxNodeSize: Int
nodeSerializer val nodeSerializer: NodeSerializer
rootRecid val rootRecid: Long
rootRecidRecid val rootRecidRecid: Long
size val size: Int
store val store: Store
valueInline val valueInline: Boolean
valueNodeSerializer val valueNodeSerializer: GroupSerializer<Any>
valueSerializer val valueSerializer: GroupSerializer<V>
values val values: MutableCollection<V?>


assertCurrentThreadUnlocked fun assertCurrentThreadUnlocked(): Unit
btreeEntry fun btreeEntry(key: K, valueOrig: V?): MutableEntry<K, V?>
ceilingEntry fun ceilingEntry(key: K?): MutableEntry<K, V>?
ceilingKey fun ceilingKey(key: K?): K?
checkThreadSafe fun checkThreadSafe(): Unit

checks all subcomponents, if this component is really thread safe, and throws an exception if not thread safe

clear fun clear(): Unit
close fun close(): Unit
comparator fun comparator(): Comparator<in K>?
containsKey fun containsKey(key: K): Boolean
containsValue fun containsValue(value: V): Boolean
descendingEntryIterator fun descendingEntryIterator(): MutableIterator<MutableEntry<K, V?>>
fun descendingEntryIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<MutableEntry<K, V?>>
descendingKeyIterator fun descendingKeyIterator(): MutableIterator<K>
fun descendingKeyIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<K>
descendingKeySet fun descendingKeySet(): NavigableSet<K>?
descendingLeafIterator fun descendingLeafIterator(hi: K?): Iterator<Node>
descendingMap fun descendingMap(): ConcurrentNavigableMap<K, V>?
descendingValueIterator fun descendingValueIterator(): MutableIterator<V?>
fun descendingValueIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<V?>
entryIterator fun entryIterator(): MutableIterator<MutableEntry<K, V?>>
fun entryIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<MutableEntry<K, V?>>
equals fun equals(other: Any?): Boolean
findHigher fun findHigher(key: K?, inclusive: Boolean): MutableEntry<K, V>?
findHigherKey fun findHigherKey(key: K?, inclusive: Boolean): K?
findLower fun findLower(key: K?, inclusive: Boolean): MutableEntry<K, V>?
findLowerKey fun findLowerKey(key: K?, inclusive: Boolean): K?
firstEntry fun firstEntry(): MutableEntry<K, V?>?
firstKey fun firstKey(): K
firstKey2 fun firstKey2(): K?
floorEntry fun floorEntry(key: K?): MutableEntry<K, V>?
floorKey fun floorKey(key: K): K?
forEach fun forEach(action: BiConsumer<in K, in V>?): Unit
forEachKey fun forEachKey(procedure: (K) -> Unit): Unit
forEachValue fun forEachValue(procedure: (V) -> Unit): Unit
get operator fun get(key: K?): V?
hashCode fun hashCode(): Int
headMap fun headMap(toKey: K?, inclusive: Boolean): ConcurrentNavigableMap<K, V>
fun headMap(toKey: K): ConcurrentNavigableMap<K, V>
higherEntry fun higherEntry(key: K?): MutableEntry<K, V>?
higherKey fun higherKey(key: K?): K?
isClosed fun isClosed(): Boolean
isEmpty fun isEmpty(): Boolean
keyIterator fun keyIterator(): MutableIterator<K>
fun keyIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<K>
lastEntry fun lastEntry(): MutableEntry<K, V?>?
lastKey fun lastKey(): K
lastKey2 fun lastKey2(): K?
listenerNotify fun listenerNotify(key: K, oldValue: V?, newValue: V?, triggered: Boolean): Unit
lock fun lock(nodeRecid: Long): Unit
lowerEntry fun lowerEntry(key: K?): MutableEntry<K, V>?
lowerKey fun lowerKey(key: K): K?
navigableKeySet fun navigableKeySet(): NavigableSet<K?>
pollFirstEntry fun pollFirstEntry(): MutableEntry<K, V?>?
pollLastEntry fun pollLastEntry(): MutableEntry<K, V?>?
prefixSubMap fun prefixSubMap(prefix: K): ConcurrentNavigableMap<K, V>
fun prefixSubMap(prefix: K, inclusive: Boolean): ConcurrentNavigableMap<K, V>
printStructure fun printStructure(out: PrintStream): Unit
put fun put(key: K?, value: V?): V?
put2 fun put2(key: K, value: V, onlyIfAbsent: Boolean): V?
putAll fun putAll(from: Map<out K?, V?>): Unit
putIfAbsent fun putIfAbsent(key: K?, value: V?): V?
putIfAbsentBoolean fun putIfAbsentBoolean(key: K?, value: V?): Boolean

Atomically associates the specified key with the given value if it is not already associated with a value.

remove fun remove(key: K?): V?
fun remove(key: Any?, value: Any?): Boolean
removeOrReplace fun removeOrReplace(key: K, expectedOldValue: V?, replaceWithValue: V?): V?
replace fun replace(key: K?, oldValue: V?, newValue: V?): Boolean
fun replace(key: K?, value: V?): V?
sizeLong fun sizeLong(): Long

map size as long number

subMap fun subMap(fromKey: K?, fromInclusive: Boolean, toKey: K?, toInclusive: Boolean): ConcurrentNavigableMap<K, V>
fun subMap(fromKey: K, toKey: K): ConcurrentNavigableMap<K, V>
tailMap fun tailMap(fromKey: K?, inclusive: Boolean): ConcurrentNavigableMap<K, V>
fun tailMap(fromKey: K): ConcurrentNavigableMap<K, V>
unlock fun unlock(nodeRecid: Long): Unit
unlockAllCurrentThread fun unlockAllCurrentThread(): Unit
valueExpand fun valueExpand(v: Any?): V?
valueIterator fun valueIterator(): MutableIterator<V?>
fun valueIterator(lo: K?, loInclusive: Boolean, hi: K?, hiInclusive: Boolean): MutableIterator<V?>
verify fun verify(): Unit

Companion Object Functions

make fun <K, V> make(keySerializer: GroupSerializer<K> = Serializer.ELSA as GroupSerializer<K>, valueSerializer: GroupSerializer<V> = Serializer.ELSA as GroupSerializer<V>, store: Store = StoreTrivial(), valueInline: Boolean = true, rootRecidRecid: Long = putEmptyRoot(store, keySerializer, if(valueInline) valueSerializer else Serializer.RECID), maxNodeSize: Int = CC.BTREEMAP_MAX_NODE_SIZE, comparator: Comparator<K> = keySerializer, isThreadSafe: Boolean = true, counterRecid: Long = 0L, hasValues: Boolean = true, modificationListeners: Array<MapModificationListener<K, V>>? = null): BTreeMap<K, V>