Package com.bigdata.btree.data

See: Description

Interface Summary

Interface	Description
IAbstractNodeData	Interface for low-level data access.
IAbstractNodeDataCoder<T extends IAbstractNodeData>	Interface for coding (compressing) an INodeData or ILeafData onto a byte[].
IChildData	Interface for data access to children of an index node.
IKeysData	Interface for access to the keys IRaba of a node or leaf in an index data structure.
ILeafData	Interface for low-level data access for the leaves of a B+-Tree.
INodeData	Interface for low-level data access for the non-leaf nodes of a B+-Tree.
ISpannedTupleCountData	Interface for low-level data access to the #of tuples spanned by a node or leaf of an index.
ITreeNodeData	Common interface for non-leaf "nodes" in a tree data structure.

Class Summary

Class	Description
AbstractLeafDataRecordTestCase	Test suite for the B+Tree ILeafData records (accessing coded data in place).
AbstractNodeDataRecordTestCase	Test suite for the B+Tree INodeData records (accessing coded data in place).
AbstractNodeOrLeafDataRecordTestCase
AbstractReadOnlyNodeData<U extends IAbstractNodeData>	Abstract base class for a read-only view of the data for B+Tree node or leaf.
DefaultLeafCoder	Default implementation for immutable ILeafData records.
DefaultNodeCoder	Default implementation for immutable INodeData records.
MockLeafData	Mock object for ILeafData used for unit tests.
MockNodeData	Mock object for INodeData.
TestAll	Aggregates test suites into increasing dependency order.
TestLeafDataRecord_CanonicalHuffman_CanonicalHuffman	Test suite for the B+Tree ILeafData records (accessing coded data in place).
TestLeafDataRecord_FrontCoded_CanonicalHuffman	Test suite for the B+Tree ILeafData records (accessing coded data in place).
TestLeafDataRecord_Simple_Simple	Test with simple coding for keys and values (no compression).
TestNodeDataRecord_CanonicalHuffman	Test suite using the CanonicalHuffmanRabaCoder to provide key compression.
TestNodeDataRecord_FrontCoded	Test suite using the FrontCodedRabaCoder to provide key compression.
TestNodeDataRecord_Simple	Test suite without key compression.

Package com.bigdata.btree.data Description

A package for the B+Tree data records. This is a binary image which can be processed directly in RAM. The on disk record is normally compressed using the compression provider for the com.bigdata.store.IRawStore. The in-memory image is a variable length immutable record encoding the persistent data for a node or leaf of a B+Tree. The binary image supports random access to all data fields, to the keys, and to the values. This means that the image can not use "packed" or nibble coded representations of integer values and can not use bit encoded representations of compression codes. However, the entire record is typically compressed by the backing store using GZip or the like, so the representation of the record on disk is quite compact.

Key compression and value compression are applied when the recorded is encoded. The representation of the compressed keys or values generally consists of a dictionary followed the code strings for the keys or values. The code strings are byte aligned so they can be accessed easily in RAM without having to scan through the image. Hu-Tucker coding is preferred to prefix coding for keys because prefix coding requires a sequential scan to process the coded keys. Huffman coding is preferred for values because it is fast and efficient and the assigned codes do not need to preserve the lexical order of the values, which is not true for the keys.