[Database] 인덱스

[Database] 인덱스

0. 들어가기 전에

성능 측정 공부를 하기전에 인덱스에 대해서 알아봤습니다.

1. 인덱스

인덱스는 무엇일까? 해당하는 단어를 사전에서 찾아보면 색인이라고 되어있다. 즉 무언가를 찾을 때 더 빨리 찾을 수 있게 하는 방법이라는 뜻이다. 좀 더 프로그래밍 관점에서 설명하자면 인덱스는 저장 성능(쓰기, 삭제, 수정) 성능을 희생하면서 읽기 성능을 높이는 방법이다.

그렇다면 이런 생각이 들 것이다. 저장 성능이 떨어진다고? 항상 좋은 것만은 아니네? 맞는 말이다. 일반적으로 인덱스는 10%의 저장소의 비율을 차지하고, 인덱스의 정렬 비용 때문에 저장 성능이 떨어진다. 따라서 인덱스는 읽기 성능을 높이기 때문에 저장 횟수보다 읽기 횟수가 더 많은 서비스에서 사용되면 좋다. 클라우드 서비스를 제외한 대부분 서비스는 읽기 비율이 저장 비율보다 압도적으로 높기 때문에 아마 대부분의 서비스가 해당이 될 것이다.

2. 인덱스의 자료구조

인덱스의 속도는 왜 빠를까? 그 답은 인덱스의 자료구조에 있다. 인덱스의 자료구조에는 대표적으로 두 가지가 있다.

2.1 Hash Table

대표적으로 속도가 빠르다고 하면 떠오르는 자료구조는 해시 테이블이 있다. 해시테이블을 간단히 설명하자면 해시 알고리즘을 통해 만든 key로 value를 저장하는 자료구조이다. key가 중복될 확률이 낮으므로 일반적으로 시간복잡도는 O(1)라고 할 수 있다.

하지만 해시 테이블은 실제로는 인덱스에서 잘 사용되지 않는 자료구조이다. 왜냐하면 일반적인 DB 작업은 단건 조회가 있지만 범위 탐색이나, 검색과 같은 작업을 해야 하는데 이럴 때는 해시 테이블 구조의 이점을 못 살리기 때문이다. 그래서 대부분의 DB는 B-tree 구조를 사용한다.

2.2 B tree

B tree는 Balanced Tree의 약자로 큰 크기의 데이터를 다루기에 좋은 데이터 구조이다. tree 구조기 때문에 시간복잡도는 O(logN)이라고 할 수 있다. B tree를 Binaray Tree라고 오해할 수 있지만 완전히 서로 다른 자료구조이다. 왜냐하면 Binary Tree는 자식 노드의 수가 2개 이하인 반면 B tree는 n차 B tree, 이런 식으로 n에 따라 최대 자식의 숫자가 달라지기 때문이다.

그렇다면 자식 노드의 수가 많아지면 어떤 점이 좋을까? 그것은 바로 트리의 높이가 줄어든다는 점이 있다. 트리의 높이가 줄어들면 탐색하는 깊이가 더 빨라져서 좋을 수 있다. 하지만 자식 노드의 수가 너무 많아지면 list와 비슷해지기 때문에 적절한 높이를 선택해야 한다.

자주 사용되는 B tree는 B-tree와 B+tree가 있다.

B-tree는 key 마다 실제 데이터 포인터를 들고 있어서 실제 데이터의 위치를 알고 있는 자료구조이다. 즉 탐색하다가 일치하는 키를 만나면 바로 실제 데이터의 위치로 갈 수 있다는 것이다.

반면에 B+tree는 리프 노드에서는 데이터 포인터가 있고 각각의 리프 노드들은 서로 Linked List로 연결되어 있다.

이에 따라 리프노드에는 부모 노드들의 키 값들이 중복되어 저장될 수 있다. 왜 이런 식으로 저장했을까? 바로 범위 탐색에 대한 성능이 좋다는 점이 있다. B-tree는 부등호 연산과 같이 범위로 검색하는 명령이 들어오면 하나의 key 값에서 바로 데이터로 접근하기 때문에 여러 개의 key에 접근하려면 탐색을 많이 해야 한다. 반면 B+tree는 리프노드까지 탐색해서 인접한 데이터의 위치를 알고 있으므로 범위탐색을 하는 데 유리하다.

실제로 MySQL의 InnoDB를 포함해서 대부분의 DBMS에서 이런 구조를 채택하고 있다.

3. 주의점

인덱스를 설정할 때는 카디널리티를 고려해야 한다. 카티널리티란 저장된 데이터 중 서로 다른 데이터라고 이해하면 쉽다. 예를 들어 사람 이름과 성별에서 각각의 카디널리티를 측정해 보면 사람 이름은 성별보다 더 다양하므로 사람 이름의 카디널리티가 성별의 카디널리티보다 높다고 할 수 있다.

※ 참고

• B 트리

• 쉬운코드 - 유튜브

• Real MySQL8.0