Package org.apache.hadoop.hbase.io.hfile
Class HFileBlockIndex.BlockIndexReader
java.lang.Object
org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexReader
- All Implemented Interfaces:
HeapSize
- Direct Known Subclasses:
HFileBlockIndex.ByteArrayKeyBlockIndexReader
,HFileBlockIndex.CellBasedKeyBlockIndexReader
- Enclosing class:
- HFileBlockIndex
The reader will always hold the root level index in the memory. Index blocks at all other
levels will be cached in the LRU cache in practice, although this API does not enforce that.
All non-root (leaf and intermediate) index blocks contain what we call a "secondary index": an array of offsets to the entries within the block. This allows us to do binary search for the entry corresponding to the given key without having to deserialize the block.
-
Field Summary
Modifier and TypeFieldDescriptionprotected int[]
protected long[]
protected int
protected long
protected int
protected int
protected int
The number of levels in the block index tree. -
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionprotected abstract void
add
(byte[] key, long offset, int dataSize) (package private) static int
binarySearchNonRootIndex
(Cell key, ByteBuff nonRootIndex, CellComparator comparator) Performs a binary search over a non-root level index block.protected abstract long
calculateHeapSizeForBlockKeys
(long heapSize) void
Verifies that the block index is non-empty and throws anIllegalStateException
otherwise.(package private) static byte[]
getNonRootIndexedKey
(ByteBuff nonRootIndex, int i) The indexed key at the ith position in the nonRootIndex.int
Returns the number of root-level blocks in this block indexint
getRootBlockDataSize
(int i) long
getRootBlockOffset
(int i) long
heapSize()
Return the approximate 'exclusive deep size' of implementing object.protected abstract void
initialize
(int numEntries) abstract boolean
isEmpty()
Returns true if the block index is empty.abstract BlockWithScanInfo
loadDataBlockWithScanInfo
(ExtendedCell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other scan info such as the key that starts the next HFileBlock.(package private) static int
locateNonRootIndexEntry
(ByteBuff nonRootBlock, Cell key, CellComparator comparator) Search for one key using the secondary index in a non-root block.abstract Cell
midkey
(HFile.CachingBlockReader cachingBlockReader) An approximation to theHFile
's mid-key.void
readMultiLevelIndexRoot
(HFileBlock blk, int numEntries) Read the root-level metadata of a multi-level block index.void
readRootIndex
(DataInput in, int numEntries) Read in the root-level index from the given input stream.readRootIndex
(HFileBlock blk, int numEntries) Read in the root-level index from the given input stream.int
rootBlockContainingKey
(byte[] key, int offset, int length) Finds the root-level index block containing the given key.abstract int
rootBlockContainingKey
(byte[] key, int offset, int length, CellComparator comp) Finds the root-level index block containing the given key.abstract int
Finds the root-level index block containing the given key.seekToDataBlock
(ExtendedCell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) Return the data block which contains this key.
-
Field Details
-
blockOffsets
-
blockDataSizes
-
rootCount
-
midLeafBlockOffset
-
midLeafBlockOnDiskSize
-
midKeyEntry
-
searchTreeLevel
The number of levels in the block index tree. One if there is only root level, two for root and leaf levels, etc.
-
-
Constructor Details
-
BlockIndexReader
-
-
Method Details
-
isEmpty
Returns true if the block index is empty. -
ensureNonEmpty
Verifies that the block index is non-empty and throws anIllegalStateException
otherwise. -
seekToDataBlock
public HFileBlock seekToDataBlock(ExtendedCell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) throws IOException Return the data block which contains this key. This function will only be called when the HFile version is larger than 1.- Parameters:
key
- the key we are looking forcurrentBlock
- the current block, to avoid re-reading the same blockexpectedDataBlockEncoding
- the data block encoding the caller is expecting the data block to be in, or null to not perform this check and return the block irrespective of the encoding- Returns:
- reader a basic way to load blocks
- Throws:
IOException
-
loadDataBlockWithScanInfo
public abstract BlockWithScanInfo loadDataBlockWithScanInfo(ExtendedCell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) throws IOException Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other scan info such as the key that starts the next HFileBlock. This function will only be called when the HFile version is larger than 1.- Parameters:
key
- the key we are looking forcurrentBlock
- the current block, to avoid re-reading the same blockexpectedDataBlockEncoding
- the data block encoding the caller is expecting the data block to be in, or null to not perform this check and return the block irrespective of the encoding.- Returns:
- the BlockWithScanInfo which contains the DataBlock with other scan info such as nextIndexedKey.
- Throws:
IOException
-
midkey
An approximation to theHFile
's mid-key. Operates on block boundaries, and does not go inside blocks. In other words, returns the first key of the middle block of the file.- Returns:
- the first key of the middle block
- Throws:
IOException
-
getRootBlockOffset
- Parameters:
i
- from 0 to- 1
-
getRootBlockDataSize
- Parameters:
i
- zero-based index of a root-level block- Returns:
- the on-disk size of the root-level block for version 2, or the uncompressed size for version 1
-
getRootBlockCount
Returns the number of root-level blocks in this block index -
rootBlockContainingKey
Finds the root-level index block containing the given key. Key to find the comparator to be used- Returns:
- Offset of block containing
key
(between 0 and the number of blocks - 1) or -1 if this file does not contain the request.
-
rootBlockContainingKey
Finds the root-level index block containing the given key. Key to find- Returns:
- Offset of block containing
key
(between 0 and the number of blocks - 1) or -1 if this file does not contain the request.
-
rootBlockContainingKey
Finds the root-level index block containing the given key. Key to find -
getNonRootIndexedKey
The indexed key at the ith position in the nonRootIndex. The position starts at 0.- Parameters:
i
- the ith position- Returns:
- The indexed key at the ith position in the nonRootIndex.
-
binarySearchNonRootIndex
Performs a binary search over a non-root level index block. Utilizes the secondary index, which records the offsets of (offset, onDiskSize, firstKey) tuples of all entries. the key we are searching for offsets to individual entries in the blockIndex buffer the non-root index block buffer, starting with the secondary index. The position is ignored.- Returns:
- the index i in [0, numEntries - 1] such that keys[i] <= key < keys[i + 1], if keys is the array of all keys being searched, or -1 otherwise
-
locateNonRootIndexEntry
Search for one key using the secondary index in a non-root block. In case of success, positions the provided buffer at the entry of interest, where the file offset and the on-disk-size can be read. a non-root block without header. Initial position does not matter. the byte array containing the key- Returns:
- the index position where the given key was found, otherwise return -1 in the case the given key is before the first key.
-
readRootIndex
Read in the root-level index from the given input stream. Must match what was written into the root level byHFileBlockIndex.BlockIndexWriter.writeIndexBlocks(FSDataOutputStream)
at the offset that function returned.- Parameters:
in
- the buffered input stream or wrapped byte input streamnumEntries
- the number of root-level index entries- Throws:
IOException
-
initialize
-
add
-
readRootIndex
Read in the root-level index from the given input stream. Must match what was written into the root level byHFileBlockIndex.BlockIndexWriter.writeIndexBlocks(FSDataOutputStream)
at the offset that function returned.- Parameters:
blk
- the HFile blocknumEntries
- the number of root-level index entries- Returns:
- the buffered input stream or wrapped byte input stream
- Throws:
IOException
-
readMultiLevelIndexRoot
Read the root-level metadata of a multi-level block index. Based onreadRootIndex(DataInput, int)
, but also reads metadata necessary to compute the mid-key in a multi-level index.- Parameters:
blk
- the HFile blocknumEntries
- the number of root-level index entries- Throws:
IOException
-
heapSize
Description copied from interface:HeapSize
Return the approximate 'exclusive deep size' of implementing object. Includes count of payload and hosting object sizings. -
calculateHeapSizeForBlockKeys
-