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