com.orientechnologies.orient.core.index.sbtree.local

Class OSBTree<K,V>

java.lang.Object

com.orientechnologies.common.concur.resource.OSharedResourceAdaptive

com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

com.orientechnologies.orient.core.index.sbtree.local.OSBTree<K,V>

public class OSBTree<K,V>
extends ODurableComponent

This is implementation which is based on B+-tree implementation threaded tree. The main differences are:

1. Buckets are not compacted/removed if they are empty after deletion of item. They reused later when new items are added.
2. All non-leaf buckets have links to neighbor buckets which contain keys which are less/more than keys contained in current bucket
There is support of null values for keys, but values itself cannot be null. Null keys support is switched off by default if null keys are supported value which is related to null key will be stored in separate file which has only one page. Buckets/pages for usual (non-null) key-value entries can be considered as sorted array. The first bytes of page contains such auxiliary information as size of entries contained in bucket, links to neighbors which contain entries with keys less/more than keys in current bucket. The next bytes contain sorted array of entries. Array itself is split on two parts. First part is growing from start to end, and second part is growing from end to start. First part is array of offsets to real key-value entries which are stored in second part of array which grows from end to start. This array of offsets is sorted by accessing order according to key value. So we can use binary search to find requested key. When new key-value pair is added we append binary presentation of this pair to the second part of array which grows from end of page to start, remember value of offset for this pair, and find proper position of this offset inside of first part of array. Such approach allows to minimize amount of memory involved in performing of operations and as result speed up data processing.

Since:

8/7/13

Author:

Andrey Lomakin

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	OSBTree.OSBTreeCursor<K,V>
class	OSBTree.OSBTreeFullKeyCursor
static interface	OSBTree.OSBTreeKeyCursor<K>

Field Summary

Fields inherited from class com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

atomicOperationsManager, extension, performanceStatisticManager, readCache, storage, writeCache

Constructor Summary

Constructors

Constructor and Description
OSBTree(String name, String dataFileExtension, boolean durableInNonTxMode, String nullFileExtension, OAbstractPaginatedStorage storage)

Method Summary

Modifier and Type	Method and Description
void	acquireAtomicExclusiveLock() Acquires exclusive lock in the active atomic operation running on the current thread for this SB-tree.
void	clear()
void	close()
void	close(boolean flush)
void	create(OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer, OType[] keyTypes, int keySize, boolean nullPointerSupport)
void	delete()
void	deleteWithoutLoad(String name)
K	firstKey()
void	flush()
V	get(K key)
boolean	isNullPointerSupport()
OSBTree.OSBTreeCursor<K,V>	iterateEntriesBetween(K keyFrom, boolean fromInclusive, K keyTo, boolean toInclusive, boolean ascSortOrder)
OSBTree.OSBTreeCursor<K,V>	iterateEntriesMajor(K key, boolean inclusive, boolean ascSortOrder)
OSBTree.OSBTreeCursor<K,V>	iterateEntriesMinor(K key, boolean inclusive, boolean ascSortOrder)
OSBTree.OSBTreeKeyCursor<K>	keyCursor()
K	lastKey()
void	load(String name, OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer, OType[] keyTypes, int keySize, boolean nullPointerSupport)
void	put(K key, V value)
V	remove(K key)
long	size()
protected void	startOperation()
boolean	validatedPut(K key, V value, OIndexEngine.Validator<K,V> validator) Puts the given value under the given key into this tree.

Methods inherited from class com.orientechnologies.orient.core.storage.impl.local.paginated.base.ODurableComponent

acquireExclusiveLock, addFile, addPage, completeOperation, deleteFile, endAtomicOperation, getChanges, getExtension, getFilledUpTo, getFullName, getLockName, getName, isFileExists, isFileExists, loadPage, loadPage, openFile, pinPage, releasePage, setName, startAtomicOperation, truncateFile

Methods inherited from class com.orientechnologies.common.concur.resource.OSharedResourceAdaptive

acquireSharedLock, addUser, assertExclusiveLockHold, assertSharedLockHold, getUsers, isConcurrent, releaseExclusiveLock, releaseSharedLock, removeUser, tryAcquireExclusiveLock, tryAcquireSharedLock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

OSBTree

public OSBTree(String name,
               String dataFileExtension,
               boolean durableInNonTxMode,
               String nullFileExtension,
               OAbstractPaginatedStorage storage)

Method Detail

create

public void create(OBinarySerializer<K> keySerializer,
                   OBinarySerializer<V> valueSerializer,
                   OType[] keyTypes,
                   int keySize,
                   boolean nullPointerSupport)

isNullPointerSupport

public boolean isNullPointerSupport()

get

public V get(K key)

put

public void put(K key,
                V value)

validatedPut

public boolean validatedPut(K key,
                            V value,
                            OIndexEngine.Validator<K,V> validator)

Puts the given value under the given key into this tree. Validates the operation using the provided validator.

Parameters:

key - the key to put the value under.

value - the value to put.

validator - the operation validator.

Returns:

true if the validator allowed the put, false otherwise.

See Also:

OIndexEngine.Validator#validate(Object, Object, Object)

close

public void close(boolean flush)

close

public void close()

clear

public void clear()

delete

public void delete()

deleteWithoutLoad

public void deleteWithoutLoad(String name)

load

public void load(String name,
                 OBinarySerializer<K> keySerializer,
                 OBinarySerializer<V> valueSerializer,
                 OType[] keyTypes,
                 int keySize,
                 boolean nullPointerSupport)

size

public long size()

remove

public V remove(K key)

iterateEntriesMinor

public OSBTree.OSBTreeCursor<K,V> iterateEntriesMinor(K key,
                                                      boolean inclusive,
                                                      boolean ascSortOrder)

iterateEntriesMajor

public OSBTree.OSBTreeCursor<K,V> iterateEntriesMajor(K key,
                                                      boolean inclusive,
                                                      boolean ascSortOrder)

firstKey

public K firstKey()

lastKey

public K lastKey()

keyCursor

public OSBTree.OSBTreeKeyCursor<K> keyCursor()

iterateEntriesBetween

public OSBTree.OSBTreeCursor<K,V> iterateEntriesBetween(K keyFrom,
                                                        boolean fromInclusive,
                                                        K keyTo,
                                                        boolean toInclusive,
                                                        boolean ascSortOrder)

flush

public void flush()

acquireAtomicExclusiveLock

public void acquireAtomicExclusiveLock()

Acquires exclusive lock in the active atomic operation running on the current thread for this SB-tree.

startOperation

protected void startOperation()

Overrides:

startOperation in class ODurableComponent