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

Class CellBTreeMultiValueV2<K>

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.multivalue.v2.CellBTreeMultiValueV2<K>

All Implemented Interfaces:

OCellBTreeMultiValue<K>

public final class CellBTreeMultiValueV2<K>
extends ODurableComponent
implements OCellBTreeMultiValue<K>

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	Description
final class	CellBTreeMultiValueV2.OCellBTreeFullKeyCursor

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
CellBTreeMultiValueV2(String name, String dataFileExtension, String nullFileExtension, String containerExtension, 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	create(OBinarySerializer<K> keySerializer, OType[] keyTypes, int keySize, OEncryption encryption, OAtomicOperation atomicOperation)
void	delete(OAtomicOperation atomicOperation)
K	firstKey()
Stream<ORID>	get(K key)
Stream<ORawPair<K,ORID>>	iterateEntriesBetween(K keyFrom, boolean fromInclusive, K keyTo, boolean toInclusive, boolean ascSortOrder)
Stream<ORawPair<K,ORID>>	iterateEntriesMajor(K key, boolean inclusive, boolean ascSortOrder)
Stream<ORawPair<K,ORID>>	iterateEntriesMinor(K key, boolean inclusive, boolean ascSortOrder)
Stream<K>	keyStream()
K	lastKey()
void	load(String name, int keySize, OType[] keyTypes, OBinarySerializer<K> keySerializer, OEncryption encryption)
void	put(OAtomicOperation atomicOperation, K pk, ORID value)
boolean	remove(OAtomicOperation atomicOperation, K k, ORID value)
long	size()

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

CellBTreeMultiValueV2

public CellBTreeMultiValueV2(String name,
 String dataFileExtension,
 String nullFileExtension,
 String containerExtension,
 OAbstractPaginatedStorage storage)

Method Details

create

public void create(OBinarySerializer<K> keySerializer,
 OType[] keyTypes,
 int keySize,
 OEncryption encryption,
 OAtomicOperation atomicOperation)

Specified by:

create in interface OCellBTreeMultiValue<K>

get

public Stream<ORID> get(K key)

Specified by:

get in interface OCellBTreeMultiValue<K>

put

public void put(OAtomicOperation atomicOperation,
 K pk,
 ORID value)

Specified by:

put in interface OCellBTreeMultiValue<K>

close

public void close()

Specified by:

close in interface OCellBTreeMultiValue<K>

delete

public void delete(OAtomicOperation atomicOperation)

Specified by:

delete in interface OCellBTreeMultiValue<K>

load

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

Specified by:

load in interface OCellBTreeMultiValue<K>

size

public long size()

Specified by:

size in interface OCellBTreeMultiValue<K>

remove

public boolean remove(OAtomicOperation atomicOperation,
 K k,
 ORID value)

Specified by:

remove in interface OCellBTreeMultiValue<K>

iterateEntriesMinor

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

Specified by:

iterateEntriesMinor in interface OCellBTreeMultiValue<K>

iterateEntriesMajor

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

Specified by:

iterateEntriesMajor in interface OCellBTreeMultiValue<K>

firstKey

public K firstKey()

Specified by:

firstKey in interface OCellBTreeMultiValue<K>

lastKey

public K lastKey()

Specified by:

lastKey in interface OCellBTreeMultiValue<K>

keyStream

public Stream<K> keyStream()

Specified by:

keyStream in interface OCellBTreeMultiValue<K>

iterateEntriesBetween

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

Specified by:

iterateEntriesBetween in interface OCellBTreeMultiValue<K>

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 OCellBTreeMultiValue<K>