디비는 왜 빠를까

2018.09.25
마쯔노부 요시노리, 『데이터베이스를 지탱하는 기술』을 읽고

대량의 레코드에서 특정 사용자 ID를 찾는 가장 빠른 방법은 무엇일까?

책 맨 뒤의 색인 페이지처럼 (키워드, 페이지) 구조로 관리하면 빠르게 찾을 수 있다. 이것이 바로 인덱스다. 인덱스 테이블은 고정된 공간을 사용할 수 있어 데이터 양에 상관없이 빠르게 접근할 수 있다. 실제 데이터베이스는 키 값을 해시 함수에 넣어 관리하는 **해시 인덱스(hash index)**를 사용하기도 한다. O(1)의 비용으로 빠르지만, 조건이나 범위 검색, 정렬에는 부적합하다.

B+ Tree 인덱스

조건, 범위 검색이나 정렬을 위해 B+ Tree 인덱스 구조를 사용한다.

• 트리 구조: 정상을 루트(Root), 최하층을 리프(Leaf), 그 사이를 브랜치(Branch) 블록이라 부른다.
• 검색 과정: 루트에서 시작해 브랜치를 거쳐 리프 블록에 도달하면 데이터 저장 위치를 알 수 있다.
• 성능: O(logN)의 시간 복잡도를 가진다. 데이터가 많아도 전체 레코드를 순회하는 O(N)보다 훨씬 빠르다.
• 범위 검색: 리프 블록끼리 연결되어 있어 범위 스캔이 용이하다. RDBMS의 사실상 표준이다.

RDBMS에서의 인덱스 활용

• 고유성 보장: 중복 체크 비용이 적다.
• 멀티 컬럼 인덱스: 여러 컬럼을 인덱스로 지정해 AND 조건 검색을 가속화할 수 있다.
• 인덱스 병합: 각각의 결과에 대해 집합 연산을 수행해 효율적으로 동작한다.

업데이트 비용 절감

레코드가 추가될 때마다 인덱스도 갱신해야 하므로 비용이 발생한다. 랜덤 액세스 비용을 줄이기 위해 MySQL(InnoDB)은 업데이트 정보를 메모리에 임시 기록하고 나중에 한꺼번에 리프를 갱신하는 구조를 채택했다. 또한 파티션 테이블을 사용하여 병렬 갱신이 가능하게 만들어 동시성을 높이고 있다.

인덱스는 만능이 아니다. 무분별한 인덱스 생성은 오버엔지니어링이다. 기술의 원리를 이해하고 균형감 있게 사용하는 것이 중요하다.