Index란 무엇인가?
인덱스는 데이터베이스 테이블에 대한 검색 성능을 높여주는 자료 구조이다.
정말 쉬운 예로 책의 목차가 바로 인덱스이다.
두꺼운 책이 있다고 했을 때 목차가 없는 상태에서
내가 원하는 부분을 찾으려면 처음부터 끝까지 검색해 봐야 한다.
데이터베이스에선 이걸 Full scan이라고 하는데
만약 목차가 있다면 내가 찾고자 하는 부분으로 한번에 이동할 수 있을 것이다.
Index의 장단점
장점이 있으면 단점도 있는 법
간략하게 장점과 단점에 대해 알아보자.
- 장점
- 테이블 조회 속도가 빨라짐으로 인해 성능 향상을 기대할 수 있다.
- 그로 인해 전반적인 시스템의 부하를 줄일 수 있다.
- 단점
- 인덱스 관리를 위해서는 DB의 약 10%에 해당하는 저장 공간이 필요하다.
- 인덱스 관리를 위해서는 추가 작업이 필요하다.
- 인덱스를 잘못 사용하면 오히려 성능이 저하될 수도 있다.
인덱스를 사용하면 좋은 경우
-
규모가 큰 테이블
규모가 크고 데이터가 많을수록 인덱스의 장점을 더욱 살릴 수 있다.
-
INSERT, UPDATE, DELETE가 자주 발생하지 않는 칼럼.
위 세 가지는 조회뿐 아니라 별도의 추가 작업을 한다.
그래서 여기에 인덱스를 걸게 되면 성능이 오히려 저하되는 역효과가 발생한다. -
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 칼럼.
서로 다른 테이블 간의 결합 시, 정렬 시, 조건을 이용한 검색 시
이 모든 경우에 인덱스를 통해 효율을 증가시킬 수 있다. -
데이터의 중복이 적은 칼럼.
내가 원하는 데이터를 선택하기 위해서는 최대한 많은 데이터가 걸러져야 한다.
그렇지 않다면 Full scan에 가까워진다.
인덱스의 자료구조
인덱스를 구현하기 위한 대표적인 자료구조로는 해시 테이블과 B+Tree가 있는데
그전에 B-Tree에 대해 먼저 알아보자.
0. B-Tree
B-Tree는 인덱스를 이루고 있는 자료구조의 일종이다.
트리 구조는 탐색 시 짧은 시간 내에 실행할 수 있다는 장점 때문에
데이터를 유지하기 위해 자주 사용되는 구조이다.
B-Tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것.
그림에 보이는 사각 도형 하나하나를 노드라고 부른다.
그림은 루트 노드, 브랜치 노드, 리프 노드로 구성되어 있다.
B-Tree는 한 노드당 자식 노드 2개 이상이 가능하며
key 값을 이용해 찾고자 하는 데이터를 트리 구조를 이용해 찾을 수 있다.
B-Tree는 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다는 균일성을 가지고 있다.
B-Tree는 균형 트리인데 여기서 말하는 균형 트리란 루트로부터 리프까지의 거리가 일정한 구조를 말한다.
그만큼 성능이 안정화되어 있는 것이 특징이다.
하지만 처음 생성 당시 균형 트리로 시작하지만 INSERT, UPDATE, DELETE 등의 테이블 갱신이 반복되며
균형이 깨지게 되고 성능이 약화된다.
어느 정도는 자체적으로 균형을 회복하는 기능이 있긴 하나
위와 같은 테이블 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우엔
인덱스의 재구성을 통해 트리 균형을 잡는 작업이 필요하다.
1. B+Tree
B+Tree는 B-Tree의 확장 개념인데 둘의 차이점을 간략히 살펴보자면,
B-Tree의 경우 인터널 또는 브랜치 노드에 key와 data를 담을 수 있는데
B+Tree의 경우 브랜치 노드에는 key만 담아두고 data는 담지 않는다.
오직 리프 노드에만 key와 data를 저장하고 리프 노드끼리 링크드 리스트(Linked list)로 연결되어 있다.
여기서 링크드 리스트(Linked list)란?
간단히 말해서 노드를 연결시킨 자료구조를 말한다.
미리 설정한 크기가 꽉 차면 새롭게 메모리를 할당하고 for loop를 통해
기존에 있던 값을 복사해야 하는, 크기가 가변적이지 않은 일반적인 배열과 달리
링크드 리스트는 필요 시 다음 노드만 추가하면 되는 가변적인 특징을 가지고 있다.
다만 서치하거나 데이터 변경 시 원하는 노드를 바로 찾아낼 수 없다는 단점도 가지고 있다.데이터가 자주 추가되거나 가변적인 사용이 필요한 곳에는 링크드 리스트를 쓰는 것이 좋고
데이터 변경이나 탐색을 위해서라면 배열을 쓰는 것이 좋다.
B+Tree는 리프 노드를 제외하곤 데이터를 담아두지 않기 때문에 가용 메모리가 증가하게 되고
더 많은 key를 수용할 수 있게 된다.
즉 하나의 노드에 더 많은 key를 담을 수 있기 때문에 트리의 높이가 낮아지게 되는 장점이 있다.
(cache hit를 높일 수 있다.)
또 Full scan 시 리프 노드에 데이터가 모두 있기 때문에 1번의 선형 탐색만 하면 되기 때문에
B-Tree에 비해 빠르다.
아래는 B-Tree와 B+Tree를 비교한 표 그림이며
데이터라고 나온 부분은 실제 DB 데이터가 아닌 자료구조상의 value를 뜻한다.
2. 해시 테이블
해시 테이블은 이전 포스팅에서 정리해 두었다.
