디비는 왜 빠를까

대량의 레코드에서 사용자 id 가 1,234,567 인 데이터를 찾고 싶다. 어떻게 가져오는 것이 빠를까?

• 사용자 정보를 100 바이트로 관리하고 순서대로 저장한다면, id x 100byte 으로부터 100byte 를 읽어 사용하면 된다. 그러나 사용자 정보가 100byte 로 고정된다는 보장이 없고, 이러한 제약으로 인해 쓰기 시 100byte 가 넘는지 확인해야 한다. 그리고 100byte 를 전부 사용하지 않는 레코드가 많으면 공간의 낭비가 심할 것이다. 여러모로 실용성이 없다.
• 책 맨 뒤에 색인 페이지를 본적이 있는가? (키워드, 기재된 페이지)의 구조로 키워드만으로 쉽게 원하는 페이지를 쉽게 찾을 수 있다. 이와 비슷하게 사용자 id 마다 파일상의 레코드 저장 위치를 기록한 파일을 만든다면 어떨까? 이것이 바로 인덱스의 구조다.
• 이러한 인덱스 테이블은 (키 값, 데이터 위치) 가 구성 요소이므로 고정된 공간을 이용할 수 있다. 가령 인덱스 레코드를 8byte 로 고정하고 id 순으로 저장한다면, id 123 데이터의 위치를 찾기 위해 123 * 8byte 를 읽어 접근할 수 있다.
• 이러한 인덱스 테이블을 관리하면 데이터를 액세스하는데 2단계가 필요하다는 단점이 있지만, 데이터 양에 의존하지 않는 비용으로 값을 읽을 수 있는 장점이 있다.
• 인덱스 자체는 본체의 데이터와 별도로 관리하기 때문에 본체의 데이터를 업데이트할 때 인덱스를 별도로 업데이트해야 한다.

인덱스 항목은 (키 값, 데이터 위치)뿐이므로 고정된 공간을 이용할 수 있을 것이라 생각했다. 그러나 키 값이 숫자, 문자열, 날짜/시간 등 여러가지를 생각하면 고정된 공간을 담보하기 어렵다. 따라서 실제 데이터베이스는 키 값을 그대로 관리하지 않고, 해시함수에 대입하여 값과 값의 쌍을 갖는 구조를 사용한다. 이러한 것을 해시 인덱스(hash index) 라고 한다.

• 해시 계산 비용 일반적으로 O(1)이므로 빠르다. 데이터가 늘어남에 해쉬 충돌의 오버헤드가 있을 수 있지만 이는 큰 비용은 아니다.

• 그러나 이러한 해쉬 값은 조건이나 범위 검색 그리고 정렬에 부적합 하다.

  • 조건 검색: 가격이 10000원 이하의 선물들
  • 범위 검색: 제목이 Final 로 시작하는 게임 리스트
  • 정렬: 상품 가격이 싼 순서대로 표시하고 싶다.

• 참조와 업데이트에서 빠른 장점이 있지만 당연하게도 모든 문제를 해결할 수 없다. 단지 일부 용도에서만 빠르게 처리할 수 있다 정도로 생각하자.

B+ Tree 인덱스

조건, 범위의 검색이나 정렬에 빠르게 결과를 반환하는 인덱스는 없을까? 이것을 실현하고자하는 것이 B+ Tree 인덱스 구조다.

• B+ Tree 는 트리 구조이다. 구조는 정상을 루트(Root) 블록, 최하층을 리프(Leaf) 블록이라 부르며 그 사이의 브랜치(Branch) 블록이라 부른다.

  

• 루트 블록과 브랜치 블록은 키값을 바탕으로 해당 블록이 어디에 있는지에 대한 정보를 가지고 있다. 그리고 최하층의 리프 블록은 저장 위치의 정보를 가지고 있다. 따라서 인덱스 검색은 루트→ 브랜치 → 리프 순으로 순회하여 원하는 데이터를 가져온다.

• B+ Tree 는 하나의 블록에서 뻗어나가는 가지의 수가 2개 이상이기 때문에 다분기 트리라고도 부른다. 계층이(트리의 높이)가 깊은 만큼 액세스가 발생하게 된다. 이진트리의 경우 N 계층당 2^N개만 기록할 수 없기 때문에 계층이 깊어지고 그만큼 액세스 횟수가 증가하게 된다.

• B+ Tree와 같은 다분기 트리는 time complexity 가 O(logN)이 되어, 데이터가 많을 때 전체 레코드를 순회하는 방법O(N)과는 비교도 안되게 빠르다.

• B+ Tree 는 등호검색은 물론이고 부등호나 전방 일치 검색 등의 범위 검색도 브랜치를 그때마다 거쳐 나갈 필요 없이, 리프 블록을 스캔하는 것으로 연산을 완결 할 수 있다.

• B+ Tree 인덱스는 RDBMS의 사실상의 표준으로 사용되고 있다. 인덱스에서 가령 B- Tree 등의 자료구조보다 적합한 지는 설명을 생략한다.

RDBMS에서의 인덱스

• 고유성을 보장: 해시 인덱스라면 동일한 해쉬로, B+ Tree 인덱스라면 동일 리프블록에 도달하므로 적은 코스트로 쉽게 중복 체크를 할 수 있다.
• 멀티 컬럼 인덱스: 여러개의 컬럼을 인덱스로 지정하는 것도 가능하다. 이를 멀티 컬럼 인덱스 라고 한다. 가령 ID 가 100 이고 수정날짜가 2009년 9월 30이전의 것을 검색하고자 할 때 여러 컬럼이 인덱스로 지정하면 이러한 AND 조건 검색을 가속화 할 수 있다. 어떻게 멀티 컬럼 인덱스를 만들 수 있을까 생각해보자. 간단한 컨셉에 대한 정답은 여기에서 볼 수 있다.
• 인덱스 병합: 만약 부서 코드가 100번 또는 입사 년도가 2010년인 직원을 찾는다고 가정하자. 인덱스 병합으로는 먼저 각각의 결과에 대해 AND 조건과 OR 조건으로 집합 연산을 수행하고, 그 결과에 행 번호에 대해서만 데이터를 읽어 효율적인 동작을 시행한다.

업데이트 비용을 절감하기 위한 노력

• 레코드를 추가할 때 마다, 인덱스에도 데이터를 갱신해야한다. 이러한 경우 인덱스의 리프 블록 이곳저곳에 무작위에 가까운 형태로 업데이트 될 것이다. 이러한 랜덤 액세스는 비용이 크므로 이 비용을 어떻게 감소시키느냐가 성능에 있어 중요하다. Mysql(InnoDB)에서는 업데이트된 정보를 메모리나 파일등에 일시적으로 기록하고 나중에 모아서 단번에 리프를 갱신하는 구조를 채택했다.
• B+ Tree 인덱스에 값을 추가/갱신/삭제 할 경우, 인덱스의 리프 블록을 이동시킬 필요가 있다. 이를 리프 분할이라고 한다. 이러한 인덱스 재편성 처리가 완료될 때 까지 참조/갱신 처리를 차단한다. 따라서 추가/갱신/삭제에 대해 동시성이 그다지 높지 않다. Mysql(InnoDB)에서는 테이블을 내부적으로는 복수 분할 관리하는 파티션 테이블을 사용하여 병렬 갱신이 가능한 구조를 만들어 동시성을 높히고 있다.

인덱스를 이용하는 것이 항상 좋은 것은 아니다. 가끔 보수적으로 인덱스를 마구 잡는 것을 볼 수 있는데 이는 무책임한 오버엔지니어링이라고 생각한다. 모든 기술이 그러하지만 균형감 있게 적절하게 사용하는 것이 중요하다. 잘 알지 못하면 논리적인 선택이 불가능하고 감에 의한 엔지니어링을 하게 될 것이다.

데이터베이스를 지탱하는 기술를 바탕으로 정리