org.mapdb

Class BTreeMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

org.mapdb.BTreeMap<K,V>

All Implemented Interfaces:

java.io.Closeable, java.io.Serializable, java.lang.AutoCloseable, java.util.concurrent.ConcurrentMap<K,V>, java.util.concurrent.ConcurrentNavigableMap<K,V>, java.util.Map<K,V>, java.util.NavigableMap<K,V>, java.util.SortedMap<K,V>, Bind.MapWithModificationListener<K,V>

public class BTreeMap<K,V>
extends java.util.AbstractMap<K,V>
implements java.util.concurrent.ConcurrentNavigableMap<K,V>, Bind.MapWithModificationListener<K,V>, java.io.Closeable, java.io.Serializable

A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a 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 ConcurrentModificationException, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

It is possible to obtain consistent iterator by using snapshot() method.

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.)

This collection has optional size counter. If this is enabled Map size is kept in Atomic.Long variable. Keeping counter brings considerable overhead on inserts and removals. If the size counter is not enabled the size method is not a constant-time operation. Determining the current number of elements requires a traversal of the elements.

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 Map and 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 elements.

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

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BTreeMap.BNode common interface for BTree node
static class	BTreeMap.DirNode
static class	BTreeMap.KeySet<E>
static class	BTreeMap.LeafNode

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
BTreeMap(Engine engine, boolean closeEngine, long rootRecidRef, int maxNodeSize, boolean valsOutsideNodes, long counterRecid, BTreeKeySerializer keySerializer, Serializer<V> valueSerializer, int numberOfNodeMetas) Constructor used to create new BTreeMap.

Method Summary

Modifier and Type	Method and Description
java.util.Map.Entry<K,V>	ceilingEntry(K key)
K	ceilingKey(K key)
void	checkStructure()
void	clear()
void	close()
java.util.Comparator<? super K>	comparator()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
java.util.NavigableSet<K>	descendingKeySet()
java.util.concurrent.ConcurrentNavigableMap<K,V>	descendingMap()
java.util.Set<java.util.Map.Entry<K,V>>	entrySet()
java.util.Map.Entry<K,V>	firstEntry()
K	firstKey()
java.util.Map.Entry<K,V>	floorEntry(K key)
K	floorKey(K key)
V	get(java.lang.Object key)
Engine	getEngine()
java.util.concurrent.ConcurrentNavigableMap<K,V>	headMap(K toKey)
java.util.concurrent.ConcurrentNavigableMap<K,V>	headMap(K toKey, boolean inclusive)
java.util.Map.Entry<K,V>	higherEntry(K key)
K	higherKey(K key)
boolean	isEmpty()
java.util.NavigableSet<K>	keySet()
java.util.Map.Entry<K,V>	lastEntry()
K	lastKey()
java.util.Map.Entry<K,V>	lowerEntry(K key)
K	lowerKey(K key)
long	mappingCount()
void	modificationListenerAdd(Bind.MapListener<K,V> listener) Add new modification listener notified when Map has been updated
void	modificationListenerRemove(Bind.MapListener<K,V> listener) Remove registered notification listener
java.util.NavigableSet<K>	navigableKeySet()
java.util.Map.Entry<K,V>	pollFirstEntry()
java.util.Map.Entry<K,V>	pollLastEntry()
void	printTreeStructure()
V	put(K key, V value)
V	putIfAbsent(K key, V value)
V	remove(java.lang.Object key)
boolean	remove(java.lang.Object key, java.lang.Object value)
V	replace(K key, V value)
boolean	replace(K key, V oldValue, V newValue)
int	size()
long	sizeLong()
java.util.NavigableMap<K,V>	snapshot() Make readonly snapshot view of current Map.
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)
java.util.concurrent.ConcurrentNavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)
java.util.Collection<V>	values()

Methods inherited from class java.util.AbstractMap

equals, hashCode, putAll, toString

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode, putAll

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Constructor Detail

BTreeMap

public BTreeMap(Engine engine,
                boolean closeEngine,
                long rootRecidRef,
                int maxNodeSize,
                boolean valsOutsideNodes,
                long counterRecid,
                BTreeKeySerializer keySerializer,
                Serializer<V> valueSerializer,
                int numberOfNodeMetas)

Constructor used to create new BTreeMap.

Parameters:

engine - used for persistence

closeEngine - if this object was created without DB. If true shutdown everything on close method, otherwise DB takes care of shutdown

rootRecidRef - reference to root recid

maxNodeSize - maximal BTree Node size. Node will split if number of entries is higher

valsOutsideNodes - Store Values outside of BTree Nodes in separate record?

counterRecid - recid under which Atomic.Long is stored, or 0 for no counter

keySerializer - Serializer used for keys. May be null for default value.

valueSerializer - Serializer used for values. May be null for default value

numberOfNodeMetas - number of meta records associated with each BTree node

Method Detail

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

remove

public V remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

sizeLong

public long sizeLong()

Specified by:

sizeLong in interface Bind.MapWithModificationListener<K,V>

Returns:

size of map, but in 64bit long which does not overflow at 2e9 items.

mappingCount

public long mappingCount()

putIfAbsent

public V putIfAbsent(K key,
                     V value)

Specified by:

putIfAbsent in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

putIfAbsent in interface java.util.Map<K,V>

remove

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

Specified by:

remove in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

remove in interface java.util.Map<K,V>

replace

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

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

replace

public V replace(K key,
                 V value)

Specified by:

replace in interface java.util.concurrent.ConcurrentMap<K,V>

Specified by:

replace in interface java.util.Map<K,V>

comparator

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

Specified by:

comparator in interface java.util.SortedMap<K,V>

firstEntry

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

Specified by:

firstEntry in interface java.util.NavigableMap<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface java.util.SortedMap<K,V>

pollFirstEntry

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

Specified by:

pollFirstEntry in interface java.util.NavigableMap<K,V>

pollLastEntry

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

Specified by:

pollLastEntry in interface java.util.NavigableMap<K,V>

lastEntry

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

Specified by:

lastEntry in interface java.util.NavigableMap<K,V>

lowerEntry

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

Specified by:

lowerEntry in interface java.util.NavigableMap<K,V>

lowerKey

public K lowerKey(K key)

Specified by:

lowerKey in interface java.util.NavigableMap<K,V>

floorEntry

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

Specified by:

floorEntry in interface java.util.NavigableMap<K,V>

floorKey

public K floorKey(K key)

Specified by:

floorKey in interface java.util.NavigableMap<K,V>

ceilingEntry

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

Specified by:

ceilingEntry in interface java.util.NavigableMap<K,V>

ceilingKey

public K ceilingKey(K key)

Specified by:

ceilingKey in interface java.util.NavigableMap<K,V>

higherEntry

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

Specified by:

higherEntry in interface java.util.NavigableMap<K,V>

higherKey

public K higherKey(K key)

Specified by:

higherKey in interface java.util.NavigableMap<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface java.util.SortedMap<K,V>

subMap

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

Specified by:

subMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface java.util.NavigableMap<K,V>

headMap

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

Specified by:

headMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface java.util.NavigableMap<K,V>

tailMap

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

Specified by:

tailMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface java.util.NavigableMap<K,V>

subMap

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

Specified by:

subMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

subMap in interface java.util.NavigableMap<K,V>

Specified by:

subMap in interface java.util.SortedMap<K,V>

headMap

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

Specified by:

headMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

headMap in interface java.util.NavigableMap<K,V>

Specified by:

headMap in interface java.util.SortedMap<K,V>

tailMap

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

Specified by:

tailMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

tailMap in interface java.util.NavigableMap<K,V>

Specified by:

tailMap in interface java.util.SortedMap<K,V>

keySet

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

Specified by:

keySet in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

keySet in interface java.util.Map<K,V>

Specified by:

keySet in interface java.util.SortedMap<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

navigableKeySet

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

Specified by:

navigableKeySet in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

navigableKeySet in interface java.util.NavigableMap<K,V>

values

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

Specified by:

values in interface java.util.Map<K,V>

Specified by:

values in interface java.util.SortedMap<K,V>

Overrides:

values in class java.util.AbstractMap<K,V>

entrySet

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

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in interface java.util.SortedMap<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

descendingMap

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

Specified by:

descendingMap in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

descendingMap in interface java.util.NavigableMap<K,V>

descendingKeySet

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

Specified by:

descendingKeySet in interface java.util.concurrent.ConcurrentNavigableMap<K,V>

Specified by:

descendingKeySet in interface java.util.NavigableMap<K,V>

snapshot

public java.util.NavigableMap<K,V> snapshot()

Make readonly snapshot view of current Map. Snapshot is immutable and not affected by modifications made by other threads. Useful if you need consistent view on Map. Maintaining snapshot have some overhead, underlying Engine is closed after Map view is GCed. Please make sure to release reference to this Map view, so snapshot view can be garbage collected.

Returns:

snapshot

modificationListenerAdd

public void modificationListenerAdd(Bind.MapListener<K,V> listener)

Description copied from interface: Bind.MapWithModificationListener

Add new modification listener notified when Map has been updated

Specified by:

modificationListenerAdd in interface Bind.MapWithModificationListener<K,V>

Parameters:

listener - callback interface notified when map changes

modificationListenerRemove

public void modificationListenerRemove(Bind.MapListener<K,V> listener)

Description copied from interface: Bind.MapWithModificationListener

Remove registered notification listener

Specified by:

modificationListenerRemove in interface Bind.MapWithModificationListener<K,V>

Parameters:

listener - callback interface notified when map changes

getEngine

public Engine getEngine()

printTreeStructure

public void printTreeStructure()

checkStructure

public void checkStructure()

close

public void close()

Specified by:

close in interface java.io.Closeable

Specified by:

close in interface java.lang.AutoCloseable