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

[phk1128]

.

[Sung-june27]

인덱스에서는 크게 해시 테이블, B-Tree, B+Tree를 사용합니다.

해시 테이블의 경우,
key-value 형태로 데이터를 저장해 key를 통해 데이터에 바로 접근할 수 있습니다.
이로 인해, 검색 시 O(1)의 시간 복잡도를 가집니다.

B-Tree의 경우,
이진 균형 트리로, 항상 높이를 유지합니다.
한 노드에 여러 개의 키를 저장할 수 있으며, 이로 인해 여러 개의 자식을 가질 수있습니다.
각 노드에 데이터를 저장하고 있으며, 평균적으로 O(nlogn)의 시간 복잡도를 가집니다.

B+Tree는 MySQL에서 사용하는 자료구조로, B-Tree의 변형입니다.
리프노드에만 데이터를 저장하고, 리프노드는 연결리스트 형태로 연결되어 있습니다.
이로 인해, 범위 검색에 효율적이며 평균적으로 O(nlogn)의 시간 복잡도를 가집니다.

[phk1128]

인덱스는 해시 테이블, B-Tree, B+Tree 3가지 자료구조가 있습니다.

해시 테이블은 해시 함수로 키를 버킷에 매핑하여 O(1)로 동등 조건 검색이 가능합니다. 해시 함수가 입력값을 무작위로 분산 시키기 때문에 범위 검색과 정렬이 불가능 합니다.

B-Tree는 모든 노드에 데이터를 저장하는 트리 구조로 O(logn) 검색이 가능하지만, 범위 검색 시 트리 전체를 순회해야 합니다.

B+Tree는 리프 노드에만 데이터를 저장하고 리프 노드끼리 연결 리스트로 연결되어 있어 범위 검색과 정렬에 최적화 되어 있습니다.

[kysub99]

인덱스는 조회 성능을 높이기 위해 해시 테이블과 B-Tree 계열 자료구조를 사용합니다.
해시 테이블은 특정 값에 대한 빠른 조회에 적합하지만 정렬이나 범위 검색은 지원하지 않습니다.
반면 B-Tree는 균형 트리 구조로 로그 시간 탐색이 가능하고, B+Tree는 데이터를 리프 노드에만 저장하고 리프 노드를 연결해 범위 검색과 정렬에 효율적으로 동작합니다.