인덱스의 자료구조

1. 해시 테이블, Hash Table

해시 테이블, Hash Table

• (Key, Value)의 형태로 데이터를 저장하는 자료구조
• 빠른 데이터 검색이 필요할 때 유용

• (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현

• 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원

• 해시가 등호(=) 연산에만 특화되어 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색에는 적합하지 않음

2. B+Tree

B+Tree

• DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조
• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 포함
• 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만
• 리프노드들은 LinkedList로 연결
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않을 수 있음

• 부등호를 이용한 순차 검색 연산을 위해 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 식으로 BTree를 인덱스에 맞게 최적화한 것

• 시간복잡도는 O(log2n)지만 해시테이블보다 인덱싱에 더욱 적합