인덱스란 무엇이고, 어떻게 동작하나요?

[linirini]

.

[eunjungL]

인덱스는 DB 테이블에서 작업 속도 향상을 위해 사용하는 자료 구조이다. 인덱스를 사용해 모든 열에 접근할 필요 없이 빠른 탐색이 가능하다.

선택된 컬럼들의 데이터를 복사본으로 만들어둔다. 한 개의 열에 대한 키와 포인터(value)를 가지고 있으며, 키를 통해 빠르게 검색 후 포인터를 통해 바로 원본 열에 접근이 가능하다.

인덱스 자료 구조

1. 해시 테이블

   • key 값을 해시 함수를 통해 변환 후, 해당 key의 인덱스에 value를 저장

   • 등호 연산에는 적합하지만 부등호 연산에는 적합하지 않음

     key가 조금이라도 다르면 다른 해시 값이 나오기 때문에 비슷한 key끼리 모아둘 수 없음

   • 내부 데이터가 정렬되지 않아 탐색이 비효율적

2. B-Tree: 자식 노드가 2개 이상인 트리 구조

   • key의 왼쪽 자식은 항상 key보다 작은 값, 오른쪽 자식은 큰 값을 저장

     오름차순으로 정렬되기 때문에 부등호 연산의 효율이 해시 테이블보다 월등

   • 하지만 중위 순회를 사용해 순차 검색의 효율이 떨어짐

3. B+Tree: B-Tree의 구조를 개선, 리프 노드만 value를 갖도록 설계된 B-Tree
   • value 값을 저장하지 않는만큼 한 개의 노드에 더 많은 key를 저장 → 트리의 레벨이 낮음
   • 리프 노드끼리 LinkedList로 연결되어 있어 빠른 탐색 가능

[eunjungL]

참고 자료

1. https://en.wikipedia.org/wiki/Database_index
2. https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/