[DB] 데이터베이스의 INDEX

목차

 

인덱스란?

인덱스는 DBMS의 검색 성능을 높이기 위한 자료구조라고 할 수 있다. 

 

 

인덱스가 필요한 이유

일반적으로 책을 보면 마지막에 색인이라고 되어 있는 부분이 있다. 우리는 이를 통해 내가 찾고 싶은 단어가 몇 페이지에 존재하는지를 쉽게 알 수 있다. 만약 색인이 없다면 우리는 원하는 단어를 찾기 위해 책을 처음부터 살펴보면서 해당 단어가 몇 페이지에 있는지를 찾아야만 한다. 

 

데이터베이스의 인덱스는 책에 있는 색인과 유사하다. 데이터를 찾을 때 해당 데이터가 어디 위치에 있는지를 인덱스를 활용하면 빠르게 찾아낼 수 있다. 만약 인덱스를 사용하지 않는다면 테이블의 처음부터 끝까지 탐색하여 데이터를 찾아야 하는데 이를 전체 테이블 스캔(Full Table Scan)이라고 한다. 이는 튜플의 수가 많아지면 검색 시간이 매우 오래 걸린다는 단점이 있다. 이러한 전체 테이블 스캔의 단점을 보완하기 위해 인덱스를 사용한다.

 

 

인덱스의 장점과 단점

장점

• 테이블을 조회하는 속도를 향상시킬 수 있다.
• 시스템의 전반적인 부하를 줄일 수 있다.

단점

• 인덱스를 관리하기 위해 DB에 추가적인 저장공간이 필요하게 된다(약 10%).
• 인덱스를 관리하기 위한 추가 작업이 필요하다.
• 인덱스를 잘못 사용하면 오히려 성능이 저하될 수 있다.

 

 

인덱스는 언제 사용해야 좋을까?

위에서 인덱스를 잘못 사용하면 오히려 성능이 저하될 수 있다고 하였다. 이는 INSERT, DELETE, UPDATE 쿼리문의 실행과 관련이 있다. 

 

INSERT

순차적으로 정렬되어 있는 인덱스에 새로운 값을 INSERT하게 되면 정렬 상태를 유지하기 위해 중간에 값이 들어갈 수도 있다. 이럴 경우 해당 위치에 값을 넣기 위해 밑에 있는 데이터들을 한칸씩 뒤로 밀어내는 작업이 추가로 필요하게 된다. 

 

DELETE

인덱스 테이블은 실제로 값을 삭제하지 않는다. 데이터는 유지한 채 사용하지 않는다는 표시만 남겨두게 된다. 결국 데이터의 총 개수는 줄어들지 않는 것이다.

 

UPDATE

인덱스에는 UPDATE라는 개념이 없다. UPDATE 쿼리문을 실행하면 해당 데이터에 먼저 DELETE 작업을 한 후 새로운 데이터를 INSERT하게 되는 것이다. 

 

이처럼 INSERT, DELETE, UPDATE 쿼리문이 자주 실행되는 테이블이라면 인덱스를 사용했을 때 추가적인 작업들로 인해 오히려 성능이 저하될 수도 있다. 그렇기 때문에 인덱스는 다음과 같은 상황에서 사용하는 것이 바람직하다.

 

1. 규모가 작지 않은 테이블
2. INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
3. JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
4. 데이터의 중복도가 낮은 컬럼(Cardinality가 높은 컬럼)

 

인덱스의 종류

 인덱스의 종류에는 클러스터드 인덱스와 논클러스테드 인덱스가 있다.

 

클러스터드 인덱스 (Clustered Index)

• 테이블 당 1개씩만 허용된다.
• 물리적으로 행을 재배열한다. 
• PK 설정 시 그 컬럼은 자동으로 클러스터드 인덱스가 만들어진다.
• 인덱스 자체의 리프 페이지가 곧 데이터이다. 즉 테이블 자체가 인덱스이다. (따로 인덱스 페이지를 만들지 않는다)
• 데이터 입력, 수정, 삭제 시 항상 정렬 상태를 유지한다.
• 논클러스터드 인덱스보다 검색 속도는 더 빠르다. 하지만 데이터의 입력, 수정, 삭제는 느리다.

 

논클러스터드 인덱스 (Nonclustered Index)

• 테이블 당 약 240개의 인덱스를 만들 수 있다.
• 인덱스 페이지는 로그 파일에 저장된다.
• 레코드의 원본은 정렬되지 않고, 인덱스 페이지만 정렬된다.
• 인덱스 자체의 리프 페이지는 데이터가 아니라 데이터가 위치하는 포인터이기 때문에 클러스터드보다 검색 속도는 더 느리지만 데이터의 입력, 수정, 삭제는 더 빠르다.
• 인덱스를 생성할 때 데이터 페이지는 그냥 둔 상태에서 별도의 인덱스 페이지를 따로 만들기 때문에 용량을 더 차지한다. 

 

즉 클러스터드 인덱스는 데이터의 위치를 바로 알기 때문에 그 데이터로 바로 접근할 수 있고, 논클러스터드 인덱스는 인덱스 페이지를 한 번 거쳐서 데이터에 접근하는 방식이다.

 

 

인덱스에 사용되는 자료구조 (B-Tree와 B+Tree)

일반적으로 인덱스에서 가장 많이 사용되는 자료구조에는 B-Tree와 B-Tree의 단점을 개선시킨 B+Tree가 있다. 여기에서 B는 Balanced를 의미하는데 이러한 균형 트리를 사용하는 이유는 뭘까?

 

일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도로 O(logN)을 갖지만, 트리가 편향된 경우 최악의 시간 복잡도로 O(N)을 갖게 된다. 

root node부터 탐색을 한다고 가정하고, 왼쪽처럼 편향된 트리에서 leaf node까지 탐색한다면 모든 노드를 방문하기 때문에 O(N)의 시간이 걸리게 된다. 이러한 단점을 보완하기 위해 항상 밸런스를 유지하는 트리가 필요하다. 오른쪽 트리처럼 밸런스를 유지하면 최악의 경우에도 O(logN)의 시간이 보장된다.

 

B-Tree

B-Tree의 형태

• 최상위 노드를 Root 노드라고 한다.
• 중간에 위치한 노드들을 Branch 노드라고 한다.
• 맨 말단에 위치한 노드를 Leaf 노드라고 한다.
• 하나의 노드에 매달린 자식 노드는 2개 이상 가능하다.
• Key-Value 값들은 Key를 기준으로 항상 오름차순으로 정렬되어 있다.
• 균형 트리(Balanced Tree)로 루트 노드에서 리프 노드까지의 거리가 모두 동일하다.

 

B-Tree의 예시

 

B-Tree에 대한 자세한 설명 : https://rebro.kr/169

B-Tree 시뮬레이션 : https://www.cs.usfca.edu/~galles/visualization/BTree.html

 

 

B+Tree

B+Tree는 B-Tree의 단점을 개선한 자료구조다. B+Tree의 노드는 B-Tree의 노드와 다르게 브랜치 노드는 Value에 대한 정보가 존재하지 않고 단순히 Key값만 존재한다. 가장 아래에 있는 Leaf 노드에서만 Value를 관리한다. Left 노드들은 LinkedList 구조로 서로를 참조하고 있기 때문에 B-Tree에 비하여 노드 순회가 쉽다. B+Tree는 브랜치 노드에 Value가 없기 때문에 B-Tree에 비해 차지하는 메모리가 적지만, Value를 찾기 위해선 리프 노드까지 이동해야 한다.

 

• 리프 노드를 제외한 노드들은 Key와 참조에 대한 정보만 가진다.
• Value는 리프 노드에 존재한다.
• 리프 노드들은 LinkedList 구조로 서로를 참조하고 있으므로 B-Tree에 비해 노드 순회가 쉽다.
• 브랜치 노드와 리프 노드에 모두 Key가 존재하므로 Key 중복이 발생한다.

B+Tree의 예시

B-Tree에 대한 자세한 설명 : https://rebro.kr/167

B-Tree 시뮬레이션 : https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

 

 

B-Tree와 B+Tree 비교

구분	B-Tree	B+Tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 Key를 많이 담을 수 있음)
풀 스캔시 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

References

- https://junghn.tistory.com/entry/DB-%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EC%99%80-%EB%84%8C%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EA%B0%9C%EB%85%90-%EC%B4%9D%EC%A0%95%EB%A6%AC

- https://steady-coding.tistory.com/536

- https://code-lab1.tistory.com/46

- https://kyungyeon.dev/posts/66

- https://velog.io/@kjh03160/DB-Index

- https://rebro.kr/167

- https://junhyunny.github.io/information/data-structure/db-index-data-structure/

- https://zorba91.tistory.com/293