com.bigdata.btree.raba
Class AbstractKeyBuffer

java.lang.Object
  com.bigdata.btree.raba.AbstractKeyBuffer

All Implemented Interfaces:

IRaba, Iterable<byte[]>

Direct Known Subclasses:

MutableKeyBuffer

public abstract class AbstractKeyBuffer
extends Object
implements IRaba

Class with implementations supporting mutable and immutable variable length byte[] keys.

Version:

$Id: AbstractKeyBuffer.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

TODO:

supporting a scalar int32 key natively would provide better performance for an object index. once it is up to int64, the byte[] approach could in fact be better on 32-bit hardware., explore the use of sparse buffers that minimize copying for more efficient management of large #s of keys - how would search work for such buffers?, explore use of interpolated search. certainly we should be able to estimate the distribution of the keys when creating an immutable key buffer and choose binary vs interpolated vs linear search based on that.

Constructor Summary

AbstractKeyBuffer()

Method Summary

protected abstract int	_binarySearch(int searchKeyOffset, byte[] searchKey) Binary search.
protected abstract int	_linearSearch(int searchKeyOffset, byte[] searchKey) Linear search.
protected abstract int	_prefixMatchLength(int prefixLength, byte[] searchKey) Test the search key against the leading prefix shared by all bytes in the key buffer.
abstract byte[]	getPrefix() Return the largest leading prefix shared by all keys.
abstract int	getPrefixLength() The length of the leading prefix shared by all keys.
Iterator<byte[]>	iterator() Iterator visits the byte[] elements in the view order.

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.bigdata.btree.raba.IRaba

add, add, add, capacity, copy, get, isEmpty, isFull, isKeys, isNull, isReadOnly, length, search, set, size

Constructor Detail

AbstractKeyBuffer

public AbstractKeyBuffer()

Method Detail

_prefixMatchLength

protected abstract int _prefixMatchLength(int prefixLength,
                                          byte[] searchKey)

Test the search key against the leading prefix shared by all bytes in the key buffer.

Parameters:

prefixLength - The length of the prefix shared by all keys in the buffer.

searchKey - The search key.

Returns:

Zero iff all bytes match and otherwise the insert position for the search key in the buffer. The insert position will be before the first key iff the search key is less than the prefix (-1) and will be after the last key iff the search key is greater than the prefix (-(nkeys)-1).

_linearSearch

protected abstract int _linearSearch(int searchKeyOffset,
                                     byte[] searchKey)

Linear search.

_binarySearch

protected abstract int _binarySearch(int searchKeyOffset,
                                     byte[] searchKey)

Binary search.

iterator

public Iterator<byte[]> iterator()

Description copied from interface: IRaba

Iterator visits the byte[] elements in the view order. If an element is null, then the iterator will report a null for that element.

Specified by:

iterator in interface IRaba

Specified by:

iterator in interface Iterable<byte[]>

getPrefix

public abstract byte[] getPrefix()

Return the largest leading prefix shared by all keys.

getPrefixLength

public abstract int getPrefixLength()

The length of the leading prefix shared by all keys.