Griffin: Fast Transactional Database Index with Hash and B+-Tree
<|reference_start|>Griffin: Fast Transactional Database Index with Hash and B+-Tree: Index access is one of the dominant performance factors in transactional database systems. Many systems use a B+-tree or one of its variants to handle point and range operations. This access pattern has room for performance improvement. Firstly, point operations can potentially be processed in $O(1)$ with a hash table. Secondly, to ensure serializability of transactions, range operations incur overhead from phantom avoidance techniques that involve additional processing or synchronization, such as an extra traversal of the B+-tree. To address these issues, we propose a hybrid index architecture, Griffin. For point operations, Griffin has a hash table that provides access paths in $O(1)$ time, along with a B+-tree. For phantom avoidance, Griffin employs a precision locking method, which does not involve additional traversal of the B+-tree. Despite its hybrid architecture, Griffin transparently provides linearizable operations and an interface of a single database index. We built a Griffin index combining a hash table and BwTree. Compared to a baseline index that is composed of a BwTree only, it achieves up to 3.1x higher throughput in a point operation dominant workload, and up to 5.4x higher throughput in a range operation dominant workload.<|reference_end|>
@article{nakazono2024griffin:,
    title={Griffin: Fast Transactional Database Index with Hash and B+-Tree},
    author={Sho Nakazono, Yutaro Bessho, Hideyuki Kawashima, Tatsuhiro Nakamori},
    journal={arXiv preprint arXiv:2407.13294},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.13294},
    primaryClass={cs.DB}
}