Updatable Learned Index의 구조적 특성에 따른 인덱스 크기와 성능 관계 분석 = An Analysis of the Relationship Between Index Size and Performance Based on Structural Characteristics of Updatable Learned Indexes

국문 초록 (Abstract)

Learned Index는 기계 학습을 데이터 인덱스 구조에 적용하여 데이터 분포를 학습하고 탐색 성능을 향상시키는 기법이다. 기존 Learned Index는 데이터 분포 변경 시 모델 재학습이 필요해 실시간 업데이트를 지원하지 못하는 한계가 있어, Updatable Learned Index 연구가 활발히 진행되고 있다. 본 논문은 In-place 방식에 집중하며, 이는 인덱스 생성 시 리프 노드에 여유 공간을 미리 할당하고 삽입 데이터를 이 공간에 기록하는 방식으로 동작한다. 이러한 설계는 삽입 성능을 향상시키지만 인덱스 크기를 증가시키는 요인이 된다. ALEX는 공간 효율성을 중시하여 인덱스 크기를 작게 유지하는 반면, LIPP는 더 많은 공간을 사용하여 삽입 성능을 개선하는 구조를 채택한다. 본 연구는 두 인덱스의 구조적 차이를 분석하고, 동일한 인덱스 크기 조건에서 성능을 비교하여 인덱스 크기와 성능 간의 상충관계를 정량적으로 평가한다.

다국어 초록 (Multilingual Abstract)

Learned indexes are indexing techniques that leverage machine learning models to learn data distributions and improve query performance. Traditional learned indexes do not support real-time updates, as model retraining is required when the data distribution changes. Recently, research into updatable learned indexes has increased, leading to the proposal of various index structures, which can be broadly categorized into delta-buffer-based and in-place approaches. This study focuses on the in-place approach, which preallocates gaps in leaf nodes during index construction to accommodate future insertions. While this method can improve insertion performance, it also leads to increased index size, resulting in a trade-off between index size and performance. For example, ALEX prioritizes space efficiency by minimizing index size, whereas LIPP prioritizes insertion throughput at the cost of increased space usage. In this paper, we analyze the structural characteristics of these two indexes and conduct comparative experiments under equivalent index size conditions to quantitatively evaluate how index size and structure affect performance.