[웹 프로그래머를 위한 데이터베이스를 지탱하는 기술] 2장: 인덱스로 고속 액세스 실현하기

본문은 [웹 프로그래머를 위한 데이터베이스를 지탱하는 기술]를 읽고 간단하게 정리한 글입니다. 필요에 따라 생략/수정된 부분이 있을 수 있으며, 내용이 추후 변경될 수 있습니다.

 

1. 키와 값의 페어를 관리하고 싶다

1) 전체 검색은 대량의 데이터에 적합하지 않다

• 1장에서 얘기했던 것처럼 데이터를 처음부터 끝까지 순차적으로 찾는 선형 탐색은 선형 복잡도(O(N))를 지니고 있다
  • 즉, 데이터 건수가 N배가 되면 N배의 계산량(시간)이 걸린다
• 이는 탐색 알고리즘에서 가장 비효율적이며, 데이터 건수가 아주 작은 경우에만 사용할 수 있다

 

2) 원하는 위치까지 순식간에 도달하는 방법 생각하기

• 배열처럼 데이터를 고정 크기로 관리하면 [PK X 로우의 크기]가 로우를 저장하는 시작 위치가 된다
• 이 방법을 이용하면 특정 데이터를 빠르게 얻을 수 있다

그림 2-1

• 그러나 데이터를 고정 크기로 관리하는 것은 현실적으로 어렵다
  
  • 모든 정보가 고정 크기 안에 들어간다는 보장을 하기 어렵다
  • 필요한 속성이 생겼을 때 새롭게 추가하기 어렵다
  • 공간 낭비가 심하다

 

3) 인덱스 구조 도입하기

• 책의 색인과 유사한 인덱스를 도입하면 검색 속도를 향상시킬 수 있다
  • 책의 색인은 [키워드, 페이지]로 이루어져 있다
  • 그리고 책의 본문과 독립적인 형태로(대개 책의 맨 뒤) 관리된다
• "각 로우의 PK마다 파일 상의 시작 위치를 기록한 파일"을 만들면 빠르게 원하는 데이터를 찾을 수 있을 것이다
  • 인덱스는 [키 값, 바이트 위치]가 구성요소가 되므로 고정 길이 방식을 포맷을 취할 수 있어 빠르게 값을 구할 수 있다
  • 또한, 키 값과 바이트 위치의 두 가지 요소밖에 없으므로 크기가 무한히 증가하게 되는 일은 없다 (새로운 속성이 추가되지 않는다)
  • 키 값과 바이트 위치를 모두 unsigned integer로 관리하면 적은 크기로도 데이터를 관리할 수 있다 (4바이트로 약 40억까지 취급 가능)

그림 2-2

• 인덱스를 이용하면 액세스가 2단계 필요하다는 단점이 있지만, 데이터 양에 의존하지 않는 비용으로 값을 취할 수 있으므로 빠른 검색이 가능하다
• 인덱스를 사용하면 데이터 업데이트 비용이 증가하지만, 검색 속도를 크게 향상시킬 수 있다
  • 비용이 증가하는 까닭은 인덱스 자체는 본체의 데이터와 별도로 관리하므로 본체의 데이터를 업데이트할 때 인덱스를 별도로 업데이트해야하기 때문이다

 

4) 해시 인덱스

• 앞서 인덱스는 [키 값, 바이트 위치]로 이루어져 있다고 했는데, 실제론 키 값의 속성엔 숫자, 문자열, 날짜/시간 등이 포함될 수 있다
• 따라서 키 값을 그대로 쓰는 것이 아니라 키 값을 해시 함수에 대입하여 해시 값(key)과 값(value)을 갖는 구조가 자주 사용되며, 이를 해시 인덱스라고 한다
• 해시 계산 비용은 데이터의 양에 의존하지 않으므로 해시 인덱스를 이용한 검색은 상수 복잡도(O(1))를 지닌다
  • 상수 복잡도라 하더라도 실제론 해시 충돌 판정 및 재계산이 있으므로 데이터의 양이 증가하면 평균 처리 시간은 서서히 증가한다
• 그러나 해시 인덱스는 다음과 같은 목적으로는 사용할 수 없고, 대신 B+Tree 인덱스를 사용해야 한다
  
  • 범위 검색
  • 정렬

 

 

2. 인덱스의 기본 B+Tree

1) B+Tree 인덱스란?

• B+Tree 인덱스는 트리 구조로서, 루트(root) 노드, 브랜치(branch) 노드, 리프(leaf) 노드로 이루어져 있다
  • 루트 노드와 브랜치 노드는 검색의 키인 PK에 대해 해당 블록이 어느 노드에 있는지에 대한 정보를 가지고 있다
  • 최하층의 리프 노드는 물리적인 저장 위치에 대한 정보를 가지고 있다
  • 인덱스 검색 시에는 루트 -> 브랜치 -> 리프 순으로 도달하여 원하는 데이터를 얻을 수 있다
• 아래 그림에서 실제 데이터를 구하기 위해선 4번의 접근이 일어나고, 마지막 리프 노드에서 디스크의 주소를 읽는 것을 알 수 있다

그림 2-3

• 레코드의 양에 따라 트리의 구성은 달라질 수 있다
  • 레코드 수가 적으면 루트가 브랜치를 겸하며, 루트와 리프밖에 없는 패턴도 존재한다
  • 레코드 수가 매우 많은 경우엔 브랜치 아래에 브랜치가 들어가는 4계층 이상의 구성이 될 수도 있다
  • 레코드 수가 많아질 수록 브랜치 층도 늘어나고 계층도 늘어나게 될 것이다

 

2) 다분기 트리와 이진 트리

• 브랜치 및 리프의 분기 개수가 두 개밖에 없는 것을 이진 트리라고 한다
  • 이진 트리는 레코드 수 N당 탐색에 필요한 계산량이 O(log2N)이다
• B+Tree는 다분기 트리라고도 부르며, 분기 개수가 수십 개에서 수백 개에 걸치는 경우도 있다
  • 이렇게 분기를 많이 하는 건 계층을 줄여서 액세스 횟수를 적게 하기 위해서이다
  • B+Tree는 레코드 수 N당 탐색에 필요한 계산량이 O(logmN)이다

 

3) B+Tree와 B-Tree

• BTree 인덱스는 여러 종류가 있지만 RDBMS에서는 끝단의 리프 노드에서만 값을 관리하는 B+Tree 구조를 가장 사용되고 있다
• B-Tree라는 인덱스 구조가 있는데, 이것은 리프 노드만 아니라 브랜치 노드에서도 값을 가질 수 있는 데이터 구조다
• B+Tree의 특징
  • 루트에서 리프까지 거치치 잖으면 열의 값을 검색할 수 없다
  • 브랜치가 보다 컴팩트하게 되므로 인덱스 자체의 계층 구조를 작게 할 수 있다 (최악의 경우 액세스 횟수를 줄일 수 있다)
  • B+Tree의 리프 노드는 순차적으로 서로 연결된 연결 리스트로 이루어져 있어 범위 검색에 유리하다

데이타베이스 시스템(이석호) p.276

• B-Tree의 특징
  • 브랜치에서도 키 정보를 가지고 있다
  • 범위 검색에 불리하다
• B+Tree가 범위 검색에 유리하기 때문에 B+Tree 인덱스가 RDBMS의 사실상 표준으로 사용되고 있다

 

 

3. RDBMS에서는 어떻게 최적화를 실현하고 있는가?

1) 고유성의 보장

• 인덱스는 고유성을 보증하는 목적으로도 사용할 수 있다
• 해시 인덱스라면 동일한 PK인 경우에 반드시 동일한 해시값이 되고, B+Tree 인덱스라면 동일 리프 노드에 도달하기 때문에 적은 비용으로 쉽게 중복 체크를 할 수 있다
• 고유성이 보장된 인덱스를 고유 인덱스, 보장되지 않은 인덱스를 비고유 인덱스라고 한다
  • DB 서버에서는 고유성을 보장하려는 열에 인덱스를 지정하는 것이 필수 조건으로 되어 있거나 내부적으로 인덱스를 작성하는 것이 일반이다

 

2) 멀티 칼럼 인덱스

• 여러 조건을 지정하여 인덱스 검색을 사용하고 싶을 때 사용하는 여러 조건의 인덱스를 멀티 칼럼 인덱스라고 한다
  • 예컨대 사용자 ID와 마지막 수정 날짜를 함께 조건으로 걸어 검색하고 싶을 수 있다
• 대부분의 RDBMS는 멀티 칼럼 인덱스를 지원하고 있으며, 위와 같은 AND 조건에서 검색을 가속화할 수 있다 (비단 AND 조건 뿐만이 아니라 다른 검색 패턴에서도 유효할 수 있다)

 

3) 인덱스만을 읽는 검색

• 앞서 인덱스와 데이터의 두 번에 걸친 로딩 작업이 필요한 인덱스 검색을 설명했다
  • 먼저 인덱스를 읽은 후 인덱스가 가리키는 데이터 영역을 읽는 방식을 의미한다
• 검색 패턴에 따라 인덱스를 읽는 것만으로 처리가 완결되는 경우도 있다
  • 예를 들어 "가격이 10,000원 이하인 상품의 개수를 알고 싶다"라는 경우엔 가격 인덱스가 있으면 이 인덱스에서 [가격 <= 10,000원]의 조건에 맞는 레코드 건수를 열거하는 것만으로도 결과를 구할 수 있으므로 데이터 영역에 액세스할 필요가 없다
• 데이터베이스의 구현에 따라서는 이러한 검색 패턴에 있어 인덱스 영역만을 읽음으로써 처리를 빠르게 수행할 수 있다
  • 이러한 작업을 Index only read, Covering Index라고 부른다
  • 이 작업을 지원하지 않는 데이터베이스는 [인덱스의 리프 보기 -> 데이터 영역 읽기 -> 리프 옆에 항목 읽기 보기 -> 데이터 영역 읽기 -> ...]의 랜덤 액세스를 반복하게 된다

 

4) 인덱스 병합

• OR 조건의 검색은 하나의 인덱스로만으로는 검색에 도움이 될 수 없다
  • 예컨대 "부서 코드가 100번 또는 입사 연도가 2010년인 직원을 찾고 싶다"라는 경우를 생각해볼 수 있다
• 이때, 한 번의 검색에서 두 개 이상의 인덱스를 동시에 사용하여 각각의 결과에서 원하는 레코드를 꺼내려고 할 수 있다
  • 이러한 기능이 바로 인덱스 병합이다
• 인덱스 병합은 먼저 각 인덱스에서 각각 검색을 실시하여 대상의 행 번호를 추출한다
• 그 다음 각 결과에 대해 AND 조건과 OR 조건 등으로 집합 연산을 수행한다
• 마지막으로 남은 행 번호에 대해 실제 데이터를 읽어가는 효율적인 동작을 수행한다

 

 

4. 업데이트 비용 절감을 위한 노력

• 인덱스는 본체 데이터와 별도로 유지할 필요가 있으므로 검색 성능이 높아지는 대신 업데이트 성능이 떨어진다
• 상용 DBMS는 업데이트 비용을 최대한 떨어뜨리기 위해 다양한 최적화를 구현하고 있다
• 여기서는 B+Tree 인덱스를 예로 몇 가지 포인트를 소개하고자 한다

 

1) 디스크에 모아서 기록하기

• 레코드를 등록/삭제하는 경우엔 B+Tree 인덱스에도 값을 등록/삭제해야 한다
• 키가 아닌 일반적인 컬럼의 경우 순차적으로 등록된다는 가능성이 없고, 이는 곧 인덱스의 리프 노드가 무작위에 가까운 형태로 업데이트되어 간다는 것을 의미한다(랜덤 액세스)
  • 데이터베이스에서 변경사항을 반영하기 위해 업데이트된 순서대로 디스크에 기록하게 되면 랜덤 라이트가 많이 발생하게 된다
• 이에 업데이트된 정보를 메모리나 전용 파일 등에 일시적으로 기록한 후 나중에 모아서 한꺼번에 리프 노드를  갱신하는 구조를 취할 수 있다
  • MySQL(InnoDB)가 대표적인 예다

 

2) 병렬 갱신 성능 높이기

• B+Tree의 인덱스에 값의 추가/갱신/삭제를 할 경우 인덱스의 리프 노드가 이동하는데, 이를 리프 분할이라고 한다
• MySQL(InnoDB) 등에서는 데이터의 일관성을 위해 인덱스의 재편성 처리가 완료될 때까지 일체의 참조/갱신 처리를 차단한다
  • 이로 인해 대량의 클라이언트가 동일 테이블에 대해 일제히 추가/갱신/삭제 작업을 수행할 경우 동시성이 높아지지 않는 문제가 발생한다
• 락 프리(Lock Free) 알고리즘이나 파티션 테이블 등 다양한 방법을 통해 병렬 갱신의 성능을 높일 수 있다
  • 파티션 테이블이란 사용자에게는 테이블이 한 개로 보이지만, 내부적으로는 복수로 분할 관리되는 테이블을 의미한다
  • 인덱스도 복수로 구분하고 있으므로 병렬 갱신이 가능하다

 

 

5. 요약

• 인덱스를 사용하면 검색 속도가 향상된다
• 하지만, 인덱스를 사용하면 항상 좋은 것만은 아니다
  • 데이터 크기가 증가하고 인덱스를 업데이트하기 위해 불필요한 처리가 필요하다
  • 따라서 인덱스를 함부로 부여하는 것이 아니라 필요한 것에 대해 균형 있게 부여해야 한다
• 어떤 항목이 인덱스에 적합하고, 어떤 항목이 적합하지 않은지를 판단하기 위해서는 사전 설계가 중요하다