B+ trees에서의 embedding 기법들에 대한 실험적 분석

Abstract

Main-memory의 크기가 커짐에 따라 in-memory database system에 관한 관심이 커지고 있다. Index structure의 성능은 database의 성능에 직결되기 때문에 효율적인 index structure에 관한 연구가 활발히 진행되었다. 최근에 제안된 B+tree 기반의 index인 D-tree는 search 및 insert 연산을 위한 분기 문제를 풀기 위하여 사용할 알고리즘이나, node 내에 key를 저장하는 방식에 있어서 다양한 선택지를 가지고 있지만, 정확히 어떤 상황에서 어떤 알고리즘이나 key 저장 방식이 가장 좋은 성능을 보여주는지에 대해서 밝혀내지 못하였다.본 연구에서는 랜덤하게 생성한 데이터셋을 이용한 실험을 통하여 key pointer 대신에 key 값의 일부분을 저장하여 pointer access를 줄이는 embedding 기법의 효과를 검증하고, search 연산의 경우 leaf node에서는 embedding 기법을 사용하지 않는 것이, branch node에서는 대부분의 경우 simple embedding 기법을 사용하는 것이, 그리고 데이터셋의 분포가 sparse한 경우에는 variant bit embedding 계열의 기법이 가장 좋은 성능을 보인다는 것을 밝혔다. 또한, insert 연산의 경우, 대체적으로 variant bit embedding 계열의 기법이 가장 좋은 성능을 보임을 밝혔다.

As main-memory grows in size, the interest in in-memory database systems also grows. Since the performance of the index structure is directly related to the performance of the database, studies on efficient index structures have been actively conducted. Recently proposed B+ tree based index structure, the D-tree, has various choices in which algorithm to use to solve the branching problem for a search operation, or how to store a key in the node. However, it is not clear which algorithm or method to store a key performs best. By conducting an experiment with randomly generated data set, this paper verifies the effect of embedding methods that reduce pointer access by storing a portion of key value instead of key pointer. Also, we found that not using an embedding methods performs best in leaf node. In branch node, simple embedding method generally shows good performance while variant bit embedding method works efficiently when the distribution of data set is sparse. Furthermore, variant bit embedding method shows good performance in most of the insert experiment.