인덱스에서 사용하는 자료구조를 설명해주세요.

[linirini]

.

[PgmJun]

해시 테이블

해시 테이블은 키를 해시 함수를 통해 계산하여 인덱스 위치에 데이터를 저장하는 자료구조이다. 이를 통해 데이터에 대한 빠른 접근을 가능하게 하며, 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있다. 하지만 해시 테이블은 순서가 없기 때문에 범위 쿼리나 정렬된 데이터를 필요로 하는 경우에는 적합하지 않다.

B-트리

B-트리는 데이터베이스와 파일 시스템에서 자주 사용되는 균형 이진 트리 구조이다. 노드가 여러 자식을 가질 수 있어 높은 차수의 트리를 형성하고, 각 노드는 정렬된 키를 포함한다. B-트리는 데이터를 검색, 삽입, 삭제할 때 O(log n)의 시간 복잡도를 제공하며, 디스크 페이지를 효율적으로 사용할 수 있도록 설계되었다.

B+트리

B+트리는 B-트리의 변형으로, 모든 값이 리프 노드에만 저장되고 내부 노드는 검색을 위한 키만 보유하는 구조이다. 이로 인해 리프 노드들 사이에 포인터를 연결하여 범위 쿼리를 효율적으로 처리할 수 있다. B+트리는 디스크 I/O 작업을 최소화하여 성능을 최적화하며, B-트리와 마찬가지로 O(log n)의 시간 복잡도를 갖는다.