com.orientechnologies.orient.core.storage.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.storage.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 (a.lomakin-at-orientdb.com)

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, readCache, storage, writeCache

Constructor Summary

Constructors

Constructor and Description
OSBTree(String name, String dataFileExtension, 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(OAtomicOperation atomicOperation)
void	close()
void	close(boolean flush)
void	create(OAtomicOperation atomicOperation, OBinarySerializer<K> keySerializer, OBinarySerializer<V> valueSerializer, OType[] keyTypes, int keySize, boolean nullPointerSupport, OEncryption encryption)
void	delete(OAtomicOperation atomicOperation)
void	deleteWithoutLoad(OAtomicOperation atomicOperation)
K	firstKey()
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, OEncryption encryption)
void	put(OAtomicOperation atomicOperation, K key, V value)
V	remove(OAtomicOperation atomicOperation, K key)
long	size()
boolean	update(OAtomicOperation atomicOperation, K key, OIndexKeyUpdater<V> updater, OBaseIndexEngine.Validator<K,V> validator)
boolean	validatedPut(OAtomicOperation atomicOperation, K key, V value, OBaseIndexEngine.Validator<K,V> validator)

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

addFile, addPage, calculateInsideComponentOperation, deleteFile, executeInsideComponentOperation, getExtension, getFilledUpTo, getFullName, getLockName, getName, isFileExists, loadPageForRead, loadPageForRead, loadPageForWrite, openFile, pinPage, releasePageFromRead, releasePageFromWrite, setName, truncateFile, tryExecuteInsideComponentOperation

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

acquireExclusiveLock, 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,
               String nullFileExtension,
               OAbstractPaginatedStorage storage)

Method Detail

create

public void create(OAtomicOperation atomicOperation,
                   OBinarySerializer<K> keySerializer,
                   OBinarySerializer<V> valueSerializer,
                   OType[] keyTypes,
                   int keySize,
                   boolean nullPointerSupport,
                   OEncryption encryption)
            throws IOException

Throws:

IOException

isNullPointerSupport

public boolean isNullPointerSupport()

get

public V get(K key)

put

public void put(OAtomicOperation atomicOperation,
                K key,
                V value)

validatedPut

public boolean validatedPut(OAtomicOperation atomicOperation,
                            K key,
                            V value,
                            OBaseIndexEngine.Validator<K,V> validator)

update

public boolean update(OAtomicOperation atomicOperation,
                      K key,
                      OIndexKeyUpdater<V> updater,
                      OBaseIndexEngine.Validator<K,V> validator)

close

public void close(boolean flush)

close

public void close()

clear

public void clear(OAtomicOperation atomicOperation)

delete

public void delete(OAtomicOperation atomicOperation)
            throws IOException

Throws:

IOException

deleteWithoutLoad

public void deleteWithoutLoad(OAtomicOperation atomicOperation)

load

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

size

public long size()

remove

public V remove(OAtomicOperation atomicOperation,
                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)

acquireAtomicExclusiveLock

public void acquireAtomicExclusiveLock()

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