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.
Author
Jan Kotek
Author
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: Booleanreturns 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(): Unitchecks 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?): BooleanAtomically 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?): Booleanfun replace(key: K?, value: V?): V? |
| sizeLong |
fun sizeLong(): Longmap 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 |
| 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> |