public class BTreeMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V>, Bind.MapWithModificationListener<K,V>
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 paper
from Philip L. Lehman and S. Bing Yao. More practical aspects of BTreeMap implementation are based on notes
and demo application from Thomas Dinsdale-Young.
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.Modifier and Type | Class and Description |
---|---|
protected static interface |
BTreeMap.BNode
common interface for BTree node
|
protected static class |
BTreeMap.BTreeIterator |
protected static class |
BTreeMap.DescendingMap<K,V> |
protected static class |
BTreeMap.DirNode |
protected static class |
BTreeMap.LeafNode |
protected static class |
BTreeMap.NodeSerializer<A,B> |
protected static class |
BTreeMap.SubMap<K,V> |
protected static class |
BTreeMap.ValRef
if
valsOutsideNodes is true, this class is used instead of values. |
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
Modifier and Type | Field and Description |
---|---|
protected static int |
B_TREE_NODE_DIR_C |
protected static int |
B_TREE_NODE_DIR_L |
protected static int |
B_TREE_NODE_DIR_LR |
protected static int |
B_TREE_NODE_DIR_R |
protected static int |
B_TREE_NODE_LEAF_C |
protected static int |
B_TREE_NODE_LEAF_L |
protected static int |
B_TREE_NODE_LEAF_LR |
protected static int |
B_TREE_NODE_LEAF_R |
static Comparator |
COMPARABLE_COMPARATOR |
protected Comparator |
comparator
keys are sorted by this
|
protected Atomic.Long |
counter |
protected static Object |
EMPTY |
protected Engine |
engine
DB Engine in which entries are persisted
|
protected boolean |
hasValues
is this a Map or Set? if false, entries do not have values, only keys are allowed
|
protected BTreeKeySerializer |
keySerializer
Serializer used to convert keys from/into binary form.
|
protected List<Long> |
leftEdges |
protected int |
maxNodeSize
maximal node size allowed in this BTree
|
protected Bind.MapListener<K,V>[] |
modListeners |
protected Object |
modListenersLock |
protected LongConcurrentHashMap<Thread> |
nodeLocks
holds node level locks
|
protected Serializer<BTreeMap.BNode> |
nodeSerializer |
protected int |
numberOfNodeMetas |
protected long |
rootRecidRef
recid under which reference to rootRecid is stored
|
protected boolean |
valsOutsideNodes
store values as part of BTree nodes
|
protected Serializer<V> |
valueSerializer
Serializer used to convert keys from/into binary form
|
Constructor and Description |
---|
BTreeMap(Engine engine,
long rootRecidRef,
int maxNodeSize,
boolean valsOutsideNodes,
long counterRecid,
BTreeKeySerializer<K> keySerializer,
Serializer<V> valueSerializer,
Comparator<K> comparator,
int numberOfNodeMetas,
boolean disableLocks)
Constructor used to create new BTreeMap.
|
Modifier and Type | Method and Description |
---|---|
protected static long[] |
arrayLongPut(long[] array,
int pos,
long value) |
protected static Object[] |
arrayPut(Object[] array,
int pos,
Object value)
expand array size by 1, and put value at given position.
|
protected static void |
assertNoLocks(LongConcurrentHashMap<Thread> locks) |
Map.Entry<K,V> |
ceilingEntry(K key) |
K |
ceilingKey(K key) |
void |
clear() |
void |
close()
Closes underlying storage and releases all resources.
|
Comparator<? super K> |
comparator() |
boolean |
containsKey(Object key) |
boolean |
containsValue(Object value) |
protected static long |
createRootRef(Engine engine,
BTreeKeySerializer keySer,
Serializer valueSer,
Comparator comparator,
int numberOfNodeMetas)
creates empty root node and returns recid of its reference
|
NavigableSet<K> |
descendingKeySet() |
ConcurrentNavigableMap<K,V> |
descendingMap() |
Set<Map.Entry<K,V>> |
entrySet() |
protected int |
findChildren(Object key,
Object[] keys)
Find the first children node with a key equal or greater than the given key.
|
protected Map.Entry<K,V> |
findLarger(K key,
boolean inclusive) |
protected Fun.Tuple2<Integer,BTreeMap.LeafNode> |
findLargerNode(K key,
boolean inclusive) |
protected Map.Entry<K,V> |
findSmaller(K key,
boolean inclusive) |
Map.Entry<K,V> |
firstEntry() |
K |
firstKey() |
Map.Entry<K,V> |
floorEntry(K key) |
K |
floorKey(K key) |
V |
get(Object key) |
protected Object |
get(Object key,
boolean expandValue) |
Engine |
getEngine() |
ConcurrentNavigableMap<K,V> |
headMap(K toKey) |
ConcurrentNavigableMap<K,V> |
headMap(K toKey,
boolean inclusive) |
Map.Entry<K,V> |
higherEntry(K key) |
K |
higherKey(K key) |
boolean |
isEmpty() |
NavigableSet<K> |
keySet() |
Map.Entry<K,V> |
lastEntry() |
K |
lastKey() |
protected static void |
lock(LongConcurrentHashMap<Thread> locks,
long recid) |
Map.Entry<K,V> |
lowerEntry(K key) |
K |
lowerKey(K key) |
protected Map.Entry<K,V> |
makeEntry(Object key,
Object value) |
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
|
NavigableSet<K> |
navigableKeySet() |
protected long |
nextDir(BTreeMap.DirNode d,
Object key) |
protected void |
notify(K key,
V oldValue,
V newValue) |
Map.Entry<K,V> |
pollFirstEntry() |
Map.Entry<K,V> |
pollLastEntry() |
protected static SortedMap<String,Object> |
preinitCatalog(DB db)
hack used for DB Catalog
|
void |
printTreeStructure() |
V |
put(K key,
V value) |
protected V |
put2(K key,
V value2,
boolean putOnlyIfAbsent) |
V |
putIfAbsent(K key,
V value) |
V |
remove(Object key) |
boolean |
remove(Object key,
Object value) |
V |
replace(K key,
V value) |
boolean |
replace(K key,
V oldValue,
V newValue) |
int |
size() |
long |
sizeLong() |
NavigableMap<K,V> |
snapshot()
Make readonly snapshot view of current Map.
|
ConcurrentNavigableMap<K,V> |
subMap(K fromKey,
boolean fromInclusive,
K toKey,
boolean toInclusive) |
ConcurrentNavigableMap<K,V> |
subMap(K fromKey,
K toKey) |
ConcurrentNavigableMap<K,V> |
tailMap(K fromKey) |
ConcurrentNavigableMap<K,V> |
tailMap(K fromKey,
boolean inclusive) |
protected static void |
unlock(LongConcurrentHashMap<Thread> locks,
long recid) |
protected static void |
unlockAll(LongConcurrentHashMap<Thread> locks) |
protected V |
valExpand(Object ret) |
Collection<V> |
values() |
finalize, getClass, notify, notifyAll, wait, wait, wait
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll
public static final Comparator COMPARABLE_COMPARATOR
protected static final Object EMPTY
protected static final int B_TREE_NODE_LEAF_LR
protected static final int B_TREE_NODE_LEAF_L
protected static final int B_TREE_NODE_LEAF_R
protected static final int B_TREE_NODE_LEAF_C
protected static final int B_TREE_NODE_DIR_LR
protected static final int B_TREE_NODE_DIR_L
protected static final int B_TREE_NODE_DIR_R
protected static final int B_TREE_NODE_DIR_C
protected final long rootRecidRef
protected final BTreeKeySerializer keySerializer
protected final Serializer<V> valueSerializer
protected final Comparator comparator
protected final LongConcurrentHashMap<Thread> nodeLocks
protected final int maxNodeSize
protected final Engine engine
protected final boolean hasValues
protected final boolean valsOutsideNodes
protected final Atomic.Long counter
protected final int numberOfNodeMetas
protected final Serializer<BTreeMap.BNode> nodeSerializer
protected final Object modListenersLock
protected Bind.MapListener<K,V>[] modListeners
public BTreeMap(Engine engine, long rootRecidRef, int maxNodeSize, boolean valsOutsideNodes, long counterRecid, BTreeKeySerializer<K> keySerializer, Serializer<V> valueSerializer, Comparator<K> comparator, int numberOfNodeMetas, boolean disableLocks)
engine
- used for persistencerootRecidRef
- reference to root recidmaxNodeSize
- maximal BTree Node size. Node will split if number of entries is highervalsOutsideNodes
- Store Values outside of BTree Nodes in separate record?counterRecid
- recid under which `Atomic.Long` is stored, or `0` for no counterkeySerializer
- Serializer used for keys. May be null for default value.valueSerializer
- Serializer used for values. May be null for default valuecomparator
- Comparator to sort keys in this BTree, may be null.numberOfNodeMetas
- number of meta records associated with each BTree nodedisableLocks
- makes class thread-unsafe but bit fasterprotected static SortedMap<String,Object> preinitCatalog(DB db)
protected static long createRootRef(Engine engine, BTreeKeySerializer keySer, Serializer valueSer, Comparator comparator, int numberOfNodeMetas)
protected final int findChildren(Object key, Object[] keys)
protected long nextDir(BTreeMap.DirNode d, Object key)
public void clear()
public boolean isEmpty()
public int size()
public long sizeLong()
sizeLong
in interface Bind.MapWithModificationListener<K,V>
public V putIfAbsent(K key, V value)
putIfAbsent
in interface ConcurrentMap<K,V>
putIfAbsent
in interface Map<K,V>
public Comparator<? super K> comparator()
comparator
in interface SortedMap<K,V>
public Map.Entry<K,V> firstEntry()
firstEntry
in interface NavigableMap<K,V>
public Map.Entry<K,V> pollFirstEntry()
pollFirstEntry
in interface NavigableMap<K,V>
public Map.Entry<K,V> pollLastEntry()
pollLastEntry
in interface NavigableMap<K,V>
public Map.Entry<K,V> lowerEntry(K key)
lowerEntry
in interface NavigableMap<K,V>
public Map.Entry<K,V> floorEntry(K key)
floorEntry
in interface NavigableMap<K,V>
public Map.Entry<K,V> ceilingEntry(K key)
ceilingEntry
in interface NavigableMap<K,V>
protected Fun.Tuple2<Integer,BTreeMap.LeafNode> findLargerNode(K key, boolean inclusive)
public K ceilingKey(K key)
ceilingKey
in interface NavigableMap<K,V>
public Map.Entry<K,V> higherEntry(K key)
higherEntry
in interface NavigableMap<K,V>
public boolean containsKey(Object key)
containsKey
in interface Map<K,V>
containsKey
in class AbstractMap<K,V>
public boolean containsValue(Object value)
containsValue
in interface Map<K,V>
containsValue
in class AbstractMap<K,V>
public ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
subMap
in interface ConcurrentNavigableMap<K,V>
subMap
in interface NavigableMap<K,V>
public ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)
headMap
in interface ConcurrentNavigableMap<K,V>
headMap
in interface NavigableMap<K,V>
public ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
tailMap
in interface ConcurrentNavigableMap<K,V>
tailMap
in interface NavigableMap<K,V>
public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey)
public ConcurrentNavigableMap<K,V> headMap(K toKey)
public ConcurrentNavigableMap<K,V> tailMap(K fromKey)
public NavigableSet<K> keySet()
public NavigableSet<K> navigableKeySet()
navigableKeySet
in interface ConcurrentNavigableMap<K,V>
navigableKeySet
in interface NavigableMap<K,V>
public Collection<V> values()
public ConcurrentNavigableMap<K,V> descendingMap()
descendingMap
in interface ConcurrentNavigableMap<K,V>
descendingMap
in interface NavigableMap<K,V>
public NavigableSet<K> descendingKeySet()
descendingKeySet
in interface ConcurrentNavigableMap<K,V>
descendingKeySet
in interface NavigableMap<K,V>
public NavigableMap<K,V> snapshot()
public void modificationListenerAdd(Bind.MapListener<K,V> listener)
Bind.MapWithModificationListener
modificationListenerAdd
in interface Bind.MapWithModificationListener<K,V>
listener
- callback interface notified when map changespublic void modificationListenerRemove(Bind.MapListener<K,V> listener)
Bind.MapWithModificationListener
modificationListenerRemove
in interface Bind.MapWithModificationListener<K,V>
listener
- callback interface notified when map changespublic void close()
public Engine getEngine()
public void printTreeStructure()
protected static long[] arrayLongPut(long[] array, int pos, long value)
protected static Object[] arrayPut(Object[] array, int pos, Object value)
protected static void assertNoLocks(LongConcurrentHashMap<Thread> locks)
protected static void unlock(LongConcurrentHashMap<Thread> locks, long recid)
protected static void unlockAll(LongConcurrentHashMap<Thread> locks)
protected static void lock(LongConcurrentHashMap<Thread> locks, long recid)
Copyright © 2017. All rights reserved.