Index Types

Currently, Tajo supports only one type of index, TWO_LEVEL_BIN_TREE, shortly BST. The BST index is a kind of binary search tree which is extended to be permanently stored on disk. It consists of two levels of nodes; a leaf node indexes the keys with the offsets to data stored on HDFS, and a root node indexes the keys with the offsets to the leaf nodes.

When an index scan is started, the query engine first reads the root node and finds the search key. If it successfully finds a leaf node corresponding to the search key, it subsequently finds the search key in that leaf node. Finally, it directly reads a tuple corresponding to the search key from HDFS.