[Index] 데이터베이스 인덱스 - 인덱싱 알고리즘

데이터베이스 인덱스

---

데이터베이스의 인덱스란 추가적인 저장 공간을 사용해서 테이블 검색 속도를 향상시키는 자료구조이다. 데이터베이스 인덱스에는 데이터의 키와 해당 데이터의 물리적 위치가 저장되어 있다.

 

일반적으로 select 쿼리의 where 구문에 사용될 컬럼에 대한 조회 성능을 개선할 때 사용한다.

 

 

인덱스를 사용하는 이유

---

인덱스는 실제 크기에 비해 크기가 작다. 따라서 메모리에 적재하기가 쉽다. 실제로 주 기억장치 대비 보조 기억장치의 I/O 성능은 많이 떨어진다. 때문에 인덱스를 주 기억장치인 메모리에 적재하고, 원하는 데이터의 물리적 주소를 찾아 접근하는 방법으로 조회 성능을 개선할 수 있다.

 

만약에 인덱스를 사용하지 않으면 데이터를 탐색할 때 풀 테이블 스캔(Full Table Scan) 이 발생한다. 풀 테이블 스캔은 가장 느린 테이블 스캔 방식으로, 인덱스가 없거나 인덱스가 있어도 옵티마이저(Optimizer)가 풀 스캔으로 탐색하는 것이 더 적절하다고 판단하는 경우 수행된다.

 

 

인덱스 알고리즘

---

B-Tree 알고리즘

B-Tree 알고리즘은 메모리에 담기 어려운 큰 데이터를 다루기 위해 사용된다. 즉, 파일 시스템 혹은 데이터베이스에 적합하다.

 

B-Tree 알고리즘은 이진 탐색 트리(Binary Search Tree, BST)의 일반화된 형태이다. 이진 탐색 트리가 자식 노드가 2개 이하인 트리라면, B-Tree는 자식 노드가 2개 이상인 트리이다. 즉, 노드의 개수를 늘리고 트리의 전체 높이를 줄여서 빠른 탐색 속도를 얻을 수 있다.

 

최대 M개의 자식 노드를 가질 수 있는 B-Tree를 M차 B-Tree라고 한다. 아래 그림은 차수가 3인 3차 B-Tree이다.

 

파란색 부분은 각 노드의 Key를 나타낸다. B-Tree 알고리즘은 각 노드의 키보다 작은 값은 왼쪽에, 키보다 큰 값은 오른쪽에 저장하는 방식이다.

 

B-Tree 알고리즘은 아래와 같은 특징을 가진다.

• 각 노드는 항상 정렬된 상태를 가진다. (특정 값보다 크던 작던 간단하게 조회 가능)
• 데이터가 중복되지 않는다.
• 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
• 데이터 조회뿐 아니라 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
• 항상 같은 레벨을 가진다.
  • Self-Balanced Search Tree
  • 의도적으로 리프 노드의 레벨을 동일하게 유지
  • 한쪽으로 편향되어 빠른 탐색 속도 이점을 가지지 못하는 문제를 방지
• 하나의 노드에 많은 수의 정보를 담을 수 있다.
  • B-Tree의 노드를 페이지 또는 블록이라 부르고 노드 내의 데이터를 키 라고 부름
• 노드의 각 키는 실제 데이터의 물리적 위치를 가리키고 있는 데이터 포인터를 가지고 있다.
  • 키를 기준으로 데이터 탐색
  • 일치하는 키를 발견한 경우 데이터 포인터가 가리키는 곳으로 이동
  • 데이터베이스의 경우 컬럼의 값이 키가 되고 테이블의 행은 포인터가 됨

 

B+Tree 알고리즘

B+Tree 알고리즘은 B-Tree 알고리즘을 개선시킨 알고리즘으로, MySQL(InnoDB) 등 많은 DBMS에서 B-Tree 대신 B+Tree를 사용한다.

 

B+Tree 알고리즘은 B-Tree 알고리즘과 다르게 리프 노드의 키만 데이터 포인터를 가지고 있다. B-Tree 알고리즘은 모든 모드가 데이터를 포함하고 있다. 때문에 B-Tree에서 원하는 데이터를 얻기 위해 모든 노드를 방문해야 한다면, B+Tree 알고리즘은 리프 노드에만 데이터를 저장하고 나머지 노드는 단순하게 포인터로만 사용한다. B+Tree는 리프 노드에만 데이터가 존재하므로 노드에 더 많은 키를 보관할 수 있다. 이는 트리의 높이가 낮아짐을 의미하고, 탐색 속도가 B-Tree보다 더 향상됨을 의미한다. 다만, 이런 특징 때문에 중복된 키가 존재할 수 있다.

 

또한, B+Tree 알고리즘은 B-Tree 알고리즘과 다르게 순차 검색에 유리하다. 데이터베이스 특성상 부등호 연산이 많이 발생하는데, B-Tree 알고리즘은 트리 순회를 해야하기 때문에 부등호 연산이 조금 오래 걸린다. 이런 단점을 극복하기 위해 B+Tree 알고리즘은 리프 노드를 Linked List로 연결했다. 즉, 정렬된 상태의 리프 노드를 순차 검색할 수 있게 됐다.

 

다만, B+Tree 알고리즘은 실제 데이터에 접근하기 위해 무조건 리프 노드까지 탐색해야 한다. 따라서 운이 좋으면 금방 데이터를 찾을 수 있는 B-Tree와는 다르게, B+Tree는 고정적으로 O(logN)의 탐색 시간을 갖는다.

 

 

해시 테이블(Hash Table) 알고리즘

Key-Value 쌍으로 데이터를 저장하는 자료구조이다. Key를 사용하여 원하는 데이터에 빠르게 접근할 수 있다. 데이터의 Key를 알고 있으면 데이터에 O(1)의 시간 복잡도로 접근할 수 있다.

 

설명만 보면 가장 좋고 적합한 알고리즘인 것 같다. 하지만 실제로 많은 DBMS들은 해시 테이블을 사용하지 않는다. 이유가 뭘까? 해시 테이블은 부등호 연산에 부적합하기 때문이다. 해시 테이블의 데이터는 정렬되어 있지 않으므로 부등호 연산 시 모든 데이터에 접근해야 한다.

 

 

 

인덱스를 무조건 써야할까?

---

인덱스를 사용하면 전반적인 조회 쿼리의 성능을 향상시켜 시스템 전체의 부하를 줄일 수 있다. 하지만 제대로 사용하지 못하면 역효과를 볼 수 있다.

 

우선, 인덱스는 별도의 저장 공간을 사용한다. 이 저장 공간은 데이터베이스 전체 공간의 약 10% 라고 한다. 즉, 잘못 사용하면 불필요한 저장 공간을 낭비하게 된다.

 

또한 앞서 B-Tree를 이야기하며 말한것 처럼 조회 성능은 증가할 수 있으나, 생성/수정/삭제 작업에 대한 성능은 오히려 낮아진다. 인덱싱한 테이블이 조회보다 생성/수정/삭제 작업이 더 많이 발생하면 오히려 전체 성능이 저하될 수 있다.

 

 

인덱스 대상 컬럼 선택 기준

---

인덱스 대상 컬럼은 카디널리티(cardinality) 가 높은 컬럼을 우선적으로 선택해야 한다. 카디널리티란 데이터 집합에서 유일한 데이터의 개수를 의미한다.

 

예를 들어 대한민국 국민 테이블을 인덱싱할 때, 카디널리티가 낮은 성별 대신 카디널리티가 높은 주민번호를 대상 컬럼으로 선택하는 것이 좋다.