Package com.orientechnologies.orient.core.storage.index.sbtree.local.v2

Class OSBTreeV2<K,V>

java.lang.Object

com.orientechnologies.common.concur.resource.OSharedResourceAbstract

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

com.orientechnologies.orient.core.storage.index.sbtree.local.v2.OSBTreeV2<K,V>

All Implemented Interfaces:

OSBTree<K,V>

public class OSBTreeV2<K,V>
extends ODurableComponent
implements OSBTree<K,V>

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)

Field Summary

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

atomicOperationsManager, readCache, storage, writeCache

Fields inherited from class com.orientechnologies.common.concur.resource.OSharedResourceAbstract

lock

Constructor Summary

Constructors

Constructor	Description
OSBTreeV2(String name, String dataFileExtension, String nullFileExtension, OAbstractPaginatedStorage storage)

Method Summary

Modifier and Type	Method	Description
void	acquireAtomicExclusiveLock()	Acquires exclusive lock in the active atomic operation running on the current thread for this SB-tree.
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)
K	firstKey()
void	flush()
V	get(K key)
boolean	isNullPointerSupport()
Stream<ORawPair<K,V>>	iterateEntriesBetween(K keyFrom, boolean fromInclusive, K keyTo, boolean toInclusive, boolean ascSortOrder)
Stream<ORawPair<K,V>>	iterateEntriesMajor(K key, boolean inclusive, boolean ascSortOrder)
Stream<ORawPair<K,V>>	iterateEntriesMinor(K key, boolean inclusive, boolean ascSortOrder)
Stream<K>	keyStream()
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 k)
long	size()
boolean	update(OAtomicOperation atomicOperation, K k, OIndexKeyUpdater<V> updater, IndexEngineValidator<K,V> validator)
boolean	validatedPut(OAtomicOperation atomicOperation, K key, V value, IndexEngineValidator<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, loadOrAddPageForWrite, loadPageForRead, loadPageForWrite, openFile, releasePageFromRead, releasePageFromWrite, setName, truncateFile, tryExecuteInsideComponentOperation

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

acquireExclusiveLock, acquireSharedLock, releaseExclusiveLock, releaseSharedLock

Methods inherited from class java.lang.Object

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

Constructor Details

OSBTreeV2

public OSBTreeV2(String name,
 String dataFileExtension,
 String nullFileExtension,
 OAbstractPaginatedStorage storage)

Method Details

create

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

Specified by:

create in interface OSBTree<K,V>

Throws:

IOException

isNullPointerSupport

public boolean isNullPointerSupport()

Specified by:

isNullPointerSupport in interface OSBTree<K,V>

get

public V get(K key)

Specified by:

get in interface OSBTree<K,V>

put

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

Specified by:

put in interface OSBTree<K,V>

validatedPut

public boolean validatedPut(OAtomicOperation atomicOperation,
 K key,
 V value,
 IndexEngineValidator<K,V> validator)

Specified by:

validatedPut in interface OSBTree<K,V>

update

public boolean update(OAtomicOperation atomicOperation,
 K k,
 OIndexKeyUpdater<V> updater,
 IndexEngineValidator<K,V> validator)

Specified by:

update in interface OSBTree<K,V>

close

public void close(boolean flush)

Specified by:

close in interface OSBTree<K,V>

close

public void close()

Specified by:

close in interface OSBTree<K,V>

delete

public void delete(OAtomicOperation atomicOperation)
            throws IOException

Specified by:

delete in interface OSBTree<K,V>

Throws:

IOException

load

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

Specified by:

load in interface OSBTree<K,V>

size

public long size()

Specified by:

size in interface OSBTree<K,V>

remove

public V remove(OAtomicOperation atomicOperation,
 K k)

Specified by:

remove in interface OSBTree<K,V>

iterateEntriesMinor

public Stream<ORawPair<K,V>> iterateEntriesMinor(K key,
 boolean inclusive,
 boolean ascSortOrder)

Specified by:

iterateEntriesMinor in interface OSBTree<K,V>

iterateEntriesMajor

public Stream<ORawPair<K,V>> iterateEntriesMajor(K key,
 boolean inclusive,
 boolean ascSortOrder)

Specified by:

iterateEntriesMajor in interface OSBTree<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface OSBTree<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface OSBTree<K,V>

keyStream

public Stream<K> keyStream()

Specified by:

keyStream in interface OSBTree<K,V>

iterateEntriesBetween

public Stream<ORawPair<K,V>> iterateEntriesBetween(K keyFrom,
 boolean fromInclusive,
 K keyTo,
 boolean toInclusive,
 boolean ascSortOrder)

Specified by:

iterateEntriesBetween in interface OSBTree<K,V>

flush

public void flush()

Specified by:

flush in interface OSBTree<K,V>

acquireAtomicExclusiveLock

public void acquireAtomicExclusiveLock()

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

Specified by:

acquireAtomicExclusiveLock in interface OSBTree<K,V>