org.mapdb

Class BTreeMap<K,V>

org.mapdb.BTreeMap<K,V>

All Implemented Interfaces:

ConcurrencyAware, BTreeMapJava.ConcurrentNavigableMap2<K,V>, ConcurrentNavigableMapExtra<K,V>, MapExtra<K,V>, Verifiable

public class BTreeMap<K,V>
implements Verifiable, ConcurrencyAware, 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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BTreeMap.BTreeBoundIterator<K,V>
static class	BTreeMap.BTreeIterator<K,V>
static class	BTreeMap.Companion
static class	BTreeMap.DescendingBoundIterator<K,V>
static class	BTreeMap.DescendingIterator<K,V>

Nested classes/interfaces inherited from interface org.mapdb.ConcurrencyAware

ConcurrencyAware.DefaultImpls

Field Summary

Fields

Modifier and Type	Field and Description
static BTreeMap.Companion	Companion

Constructor Summary

Constructors

Constructor and Description

BTreeMap(GroupSerializer<K> keySerializer, GroupSerializer<V> valueSerializer, long rootRecidRecid, Store store, boolean valueInline, int maxNodeSize, java.util.Comparator<K> comparator, boolean isThreadSafe, long counterRecid, boolean hasValues, MapModificationListener<K,V>[] modificationListeners) 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.

Method Summary

Modifier and Type	Method and Description
void	assertCurrentThreadUnlocked()
java.util.Map.Entry<K,V>	btreeEntry(K key, V valueOrig)
java.util.Map.Entry<K,V>	ceilingEntry(K key)
K	ceilingKey(K key)
void	checkThreadSafe() checks all subcomponents, if this component is really thread safe, and throws an exception if not thread safe
void	clear()
void	close()
java.util.Comparator<? super K>	comparator()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
java.util.Iterator<java.util.Map.Entry>	descendingEntryIterator()
java.util.Iterator<java.util.Map.Entry>	descendingEntryIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.Iterator<K>	descendingKeyIterator()
java.util.Iterator<K>	descendingKeyIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.NavigableSet<K>	descendingKeySet()
java.util.Iterator<org.mapdb.BTreeMapJava.Node>	descendingLeafIterator(K hi)
java.util.concurrent.ConcurrentNavigableMap<K,V>	descendingMap()
java.util.Iterator<V>	descendingValueIterator()
java.util.Iterator<V>	descendingValueIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.Iterator<java.util.Map.Entry>	entryIterator()
java.util.Iterator<java.util.Map.Entry>	entryIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.Set	entrySet()
boolean	equals(java.lang.Object other)
java.util.Map.Entry<K,V>	findHigher(K key, boolean inclusive)
K	findHigherKey(K key, boolean inclusive)
java.util.Map.Entry<K,V>	findLower(K key, boolean inclusive)
K	findLowerKey(K key, boolean inclusive)
java.util.Map.Entry<K,V>	firstEntry()
K	firstKey()
K	firstKey2()
java.util.Map.Entry<K,V>	floorEntry(K key)
K	floorKey(K key)
void	forEach(java.util.function.BiConsumer<? super K,? super V> action)
void	forEachKey(Function1<? super K,Unit> procedure)
void	forEachValue(Function1<? super V,Unit> procedure)
V	get(java.lang.Object key)
java.util.Comparator<K>	getComparator()
long	getCounterRecid()
java.util.Set<java.util.Map.Entry>	getEntries()
boolean	getHasValues()
GroupSerializer<K>	getKeySerializer()
java.util.NavigableSet<K>	getKeys()
NonExistentClass	getLeftEdges() recids of left-most nodes in tree
java.util.concurrent.ConcurrentHashMap<java.lang.Long,java.lang.Long>	getLocks()
int	getMaxNodeSize()
BTreeMapJava.NodeSerializer	getNodeSerializer()
long	getRootRecid()
long	getRootRecidRecid()
int	getSize()
Store	getStore()
boolean	getValueInline()
GroupSerializer<java.lang.Object>	getValueNodeSerializer()
GroupSerializer<V>	getValueSerializer()
java.util.Collection<V>	getValues()
int	hashCode()
java.util.concurrent.ConcurrentNavigableMap<K,V>	headMap(K toKey, boolean inclusive)
java.util.concurrent.ConcurrentNavigableMap<K,V>	headMap(K toKey)
java.util.Map.Entry<K,V>	higherEntry(K key)
K	higherKey(K key)
boolean	isClosed()
boolean	isEmpty()
boolean	isThreadSafe() returns true if this is configured to be thread safe
java.util.Iterator<K>	keyIterator()
java.util.Iterator<K>	keyIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.Set	keySet()
java.util.Map.Entry<K,V>	lastEntry()
K	lastKey()
K	lastKey2()
void	listenerNotify(K key, V oldValue, V newValue, boolean triggered)
void	lock(long nodeRecid)
java.util.Map.Entry<K,V>	lowerEntry(K key)
K	lowerKey(K key)
java.util.NavigableSet<K>	navigableKeySet()
java.util.Map.Entry<K,V>	pollFirstEntry()
java.util.Map.Entry<K,V>	pollLastEntry()
java.util.concurrent.ConcurrentNavigableMap<K,V>	prefixSubMap(K prefix)
java.util.concurrent.ConcurrentNavigableMap<K,V>	prefixSubMap(K prefix, boolean inclusive)
void	printStructure(java.io.PrintStream out)
V	put(K key, V value)
V	put2(K key, V value, boolean onlyIfAbsent)
void	putAll(java.util.Map<? extends K,? extends V> from)
V	putIfAbsent(K key, V value)
boolean	putIfAbsentBoolean(K key, V value) Atomically associates the specified key with the given value if it is not already associated with a value.
V	remove(java.lang.Object key)
boolean	remove(java.lang.Object key, java.lang.Object value)
V	removeOrReplace(K key, V expectedOldValue, V replaceWithValue)
boolean	replace(K key, V oldValue, V newValue)
V	replace(K key, V value)
int	size()
long	sizeLong() map size as long number
java.util.concurrent.ConcurrentNavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
java.util.concurrent.ConcurrentNavigableMap<K,V>	subMap(K fromKey, K toKey)
java.util.concurrent.ConcurrentNavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)
java.util.concurrent.ConcurrentNavigableMap<K,V>	tailMap(K fromKey)
void	unlock(long nodeRecid)
void	unlockAllCurrentThread()
V	valueExpand(java.lang.Object v)
java.util.Iterator<V>	valueIterator()
java.util.Iterator<V>	valueIterator(K lo, boolean loInclusive, K hi, boolean hiInclusive)
java.util.Collection	values()
void	verify()

Methods inherited from interface org.mapdb.Verifiable

verify

Methods inherited from interface org.mapdb.ConcurrencyAware

checkThreadSafe, isThreadSafe

Methods inherited from interface org.mapdb.ConcurrentNavigableMapExtra

descendingEntryIterator, descendingEntryIterator, descendingKeyIterator, descendingKeyIterator, descendingValueIterator, descendingValueIterator, entryIterator, findHigher, findHigherKey, findLower, findLowerKey, getHasValues, keyIterator, keyIterator, valueIterator

Methods inherited from interface org.mapdb.MapExtra

forEach, forEachKey, forEachValue, getKeySerializer, getValueSerializer, isClosed, putIfAbsentBoolean, sizeLong

Methods inherited from interface org.mapdb.BTreeMapJava.ConcurrentNavigableMap2

firstKey2, lastKey2

Field Detail

Companion

public static BTreeMap.Companion Companion

Constructor Detail

BTreeMap

public BTreeMap(GroupSerializer<K> keySerializer,
                GroupSerializer<V> valueSerializer,
                long rootRecidRecid,
                Store store,
                boolean valueInline,
                int maxNodeSize,
                java.util.Comparator<K> comparator,
                boolean isThreadSafe,
                long counterRecid,
                boolean hasValues,
                MapModificationListener<K,V>[] modificationListeners)

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.

Parameters:

isThreadSafe - returns true if this is configured to be thread safe

Method Detail

getValueNodeSerializer

public GroupSerializer<java.lang.Object> getValueNodeSerializer()

getNodeSerializer

public BTreeMapJava.NodeSerializer getNodeSerializer()

getRootRecid

public long getRootRecid()

getLeftEdges

public NonExistentClass getLeftEdges()

recids of left-most nodes in tree

getLocks

public java.util.concurrent.ConcurrentHashMap<java.lang.Long,java.lang.Long> getLocks()

get

public V get(java.lang.Object key)

listenerNotify

public void listenerNotify(K key,
                           V oldValue,
                           V newValue,
                           boolean triggered)

valueExpand

public V valueExpand(java.lang.Object v)

put

public V put(K key,
             V value)

put2

public V put2(K key,
              V value,
              boolean onlyIfAbsent)

remove

public V remove(java.lang.Object key)

removeOrReplace

public V removeOrReplace(K key,
                         V expectedOldValue,
                         V replaceWithValue)

lock

public void lock(long nodeRecid)

unlock

public void unlock(long nodeRecid)

unlockAllCurrentThread

public void unlockAllCurrentThread()

assertCurrentThreadUnlocked

public void assertCurrentThreadUnlocked()

close

public void close()

verify

public void verify()

printStructure

public void printStructure(java.io.PrintStream out)

putAll

public void putAll(java.util.Map<? extends K,? extends V> from)

putIfAbsentBoolean

public boolean putIfAbsentBoolean(K key,
                                  V value)

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

This is equivalent to: if(cache.containsKey(key)){}cache.put(key,value);return true;}else{return false;} * except that the action is performed atomically.

Throws:

putIfAbsent

public V putIfAbsent(K key,
                     V value)

remove

public boolean remove(java.lang.Object key,
                      java.lang.Object value)

replace

public boolean replace(K key,
                       V oldValue,
                       V newValue)

replace

public V replace(K key,
                 V value)

containsKey

public boolean containsKey(java.lang.Object key)

containsValue

public boolean containsValue(java.lang.Object value)

isEmpty

public boolean isEmpty()

getSize

public int getSize()

size

public int size()

sizeLong

public long sizeLong()

map size as long number

descendingKeySet

public java.util.NavigableSet<K> descendingKeySet()

descendingMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> descendingMap()

getEntries

public java.util.Set<java.util.Map.Entry> getEntries()

entrySet

public java.util.Set entrySet()

navigableKeySet

public java.util.NavigableSet<K> navigableKeySet()

getKeys

public java.util.NavigableSet<K> getKeys()

keySet

public java.util.Set keySet()

getValues

public java.util.Collection<V> getValues()

values

public java.util.Collection values()

entryIterator

public java.util.Iterator<java.util.Map.Entry> entryIterator()

entryIterator

public java.util.Iterator<java.util.Map.Entry> entryIterator(K lo,
                                                             boolean loInclusive,
                                                             K hi,
                                                             boolean hiInclusive)

keyIterator

public java.util.Iterator<K> keyIterator()

keyIterator

public java.util.Iterator<K> keyIterator(K lo,
                                         boolean loInclusive,
                                         K hi,
                                         boolean hiInclusive)

valueIterator

public java.util.Iterator<V> valueIterator()

valueIterator

public java.util.Iterator<V> valueIterator(K lo,
                                           boolean loInclusive,
                                           K hi,
                                           boolean hiInclusive)

descendingLeafIterator

public java.util.Iterator<org.mapdb.BTreeMapJava.Node> descendingLeafIterator(K hi)

descendingEntryIterator

public java.util.Iterator<java.util.Map.Entry> descendingEntryIterator()

descendingEntryIterator

public java.util.Iterator<java.util.Map.Entry> descendingEntryIterator(K lo,
                                                                       boolean loInclusive,
                                                                       K hi,
                                                                       boolean hiInclusive)

descendingKeyIterator

public java.util.Iterator<K> descendingKeyIterator()

descendingKeyIterator

public java.util.Iterator<K> descendingKeyIterator(K lo,
                                                   boolean loInclusive,
                                                   K hi,
                                                   boolean hiInclusive)

descendingValueIterator

public java.util.Iterator<V> descendingValueIterator()

descendingValueIterator

public java.util.Iterator<V> descendingValueIterator(K lo,
                                                     boolean loInclusive,
                                                     K hi,
                                                     boolean hiInclusive)

btreeEntry

public java.util.Map.Entry<K,V> btreeEntry(K key,
                                           V valueOrig)

hashCode

public int hashCode()

equals

public boolean equals(java.lang.Object other)

isClosed

public boolean isClosed()

forEach

public void forEach(java.util.function.BiConsumer<? super K,? super V> action)

forEachKey

public void forEachKey(Function1<? super K,Unit> procedure)

forEachValue

public void forEachValue(Function1<? super V,Unit> procedure)

prefixSubMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> prefixSubMap(K prefix)

prefixSubMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> prefixSubMap(K prefix,
                                                                     boolean inclusive)

subMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                                               boolean fromInclusive,
                                                               K toKey,
                                                               boolean toInclusive)

headMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> headMap(K toKey,
                                                                boolean inclusive)

tailMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> tailMap(K fromKey,
                                                                boolean inclusive)

subMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                                               K toKey)

headMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> headMap(K toKey)

tailMap

public java.util.concurrent.ConcurrentNavigableMap<K,V> tailMap(K fromKey)

comparator

public java.util.Comparator<? super K> comparator()

firstEntry

public java.util.Map.Entry<K,V> firstEntry()

lastEntry

public java.util.Map.Entry<K,V> lastEntry()

firstKey2

public K firstKey2()

lastKey2

public K lastKey2()

firstKey

public K firstKey()

lastKey

public K lastKey()

pollFirstEntry

public java.util.Map.Entry<K,V> pollFirstEntry()

pollLastEntry

public java.util.Map.Entry<K,V> pollLastEntry()

findHigher

public java.util.Map.Entry<K,V> findHigher(K key,
                                           boolean inclusive)

findLower

public java.util.Map.Entry<K,V> findLower(K key,
                                          boolean inclusive)

findHigherKey

public K findHigherKey(K key,
                       boolean inclusive)

findLowerKey

public K findLowerKey(K key,
                      boolean inclusive)

lowerEntry

public java.util.Map.Entry<K,V> lowerEntry(K key)

lowerKey

public K lowerKey(K key)

floorEntry

public java.util.Map.Entry<K,V> floorEntry(K key)

floorKey

public K floorKey(K key)

ceilingEntry

public java.util.Map.Entry<K,V> ceilingEntry(K key)

ceilingKey

public K ceilingKey(K key)

higherEntry

public java.util.Map.Entry<K,V> higherEntry(K key)

higherKey

public K higherKey(K key)

clear

public void clear()

checkThreadSafe

public void checkThreadSafe()

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

getKeySerializer

public GroupSerializer<K> getKeySerializer()

getValueSerializer

public GroupSerializer<V> getValueSerializer()

getRootRecidRecid

public long getRootRecidRecid()

getStore

public Store getStore()

getValueInline

public boolean getValueInline()

getMaxNodeSize

public int getMaxNodeSize()

getComparator

public java.util.Comparator<K> getComparator()

isThreadSafe

public boolean isThreadSafe()

returns true if this is configured to be thread safe

getCounterRecid

public long getCounterRecid()

getHasValues

public boolean getHasValues()