DB Index 에 대한 내용을 알기 전에 Index 사용 배경에 대해서 먼저 생각해보자.
[ 그림 1 ]
[ 그림 1 ] 은 MySQL Engine Architecture 를 표현한 것인데, 여기서 Index 와 관련하여 주목할 점은 Storage Engine 이다.
실제 데이터를 디스크 스토리지에 저장하거나 디스크 스토리지로부터 데이터를 읽어오는 부분은 스토리지 엔진이 전담한다.
위 인용 내용에서 알 수 있듯이 Storage Engine 은 요청에 의해 데이터를 디스크 영역에 저장하거나 불러오는 작업, 다시 말해 I/O 작업을 처리하는 역할을 맡는다.
[ 그림 2 ]
위에서 언급한 Storage Engine 의 I/O 처리는 디스크 영역에 저장된 데이터 파일에 대한 것이므로 [ 그림 2 ] 에서 알 수 있듯이 처리 속도가 상대적으로 느리다는 특징이 있다. 따라서 데이터베이스 테이블에서 데이터를 조회할 때 디스크 영역에 위치한 데이터를 여러 번에 걸쳐 요청하게 되면 처리 속도 (= 성능)에 좋지 않은 영향을 줄 수 있다.
그렇다면 Storage Engine 의 데이터 조회 과정에서 성능을 개선시키기 위해서 어떤 점을 개선해야 할까? 데이터 조회 성능을 개선시킬 수 있는 방법은 다양할 수 있지만 위에서 설명한 내용을 기준으로 봤을 때, 디스크 영역에 대한 접근 횟수를 줄이는 것을 생각해볼 수 있다. 디스크 영역에 대한 접근 횟수를 줄이기 위해서는 또 어떤 것들이 필요할까?
데이터베이스 테이블에 특정 데이터 한 건을 조회하는 상황에서, 테이블의 각 로우 별로 I/O 요청을 보내야 한다고 가정해보자. 이 때 심지어 테이블에 어떠한 정렬 기준도 없다면, 최악의 경우 해당 테이블의 row 수 만큼 I/O 요청을 해야 한다. 예를 들어, 회원 테이블에 5명이 저장되어 있고 찾는 회원 데이터가 마지막 row 에 저장되어 있다면, 5번의 I/O 요청을 보내야 하는 상황에 놓인다. 또한 테이블 내 데이터를 모두 탐색 (Full Scan) 해야 하므로, 저장된 데이터가 많아질수록 데이터 조회 소요 시간이 계속해서 길어지게 되는 구조적인 문제가 있다.
위와 반대로 만약 회원의 가입 순서에 따라 부여된 ID 를 기준으로 데이터가 정렬되어 있고, 특정 회원을 찾을 때 ID 를 기준으로 (Where user_id = ?) 조회할 수 있다면 어떨까? 이 경우에는 탐색 알고리즘에 따라서 I/O 요청 횟수가 달라진다. 먼저 순차 탐색을 하게 되면 앞서 Full Scan 상황과 같이 최악의 경우 테이블 내 데이터 수만큼 I/O 요청을 해야 할 수도 있다. 반면, 회원 ID 를 기준으로 정렬된 점을 활용해 Binary Search 를 한다면, log N(= 테이블 데이터 수) 만큼의 I/O 요청을 통해서 대상 회원 데이터를 찾을 수 있을 것이다. 이에 더 나아가 해시 알고리즘을 활용한다면 한 번에 원하는 데이터를 찾을 수도 있을 것이다. (다만 해시 알고리즘 구조 상 해시 충돌이 있는 경우 순차 탐색과 같이 최악의 경우 Full Scan 이 상황이 생길 수 있다)
DB Index 사용 배경과 관련한 위 내용을 기반으로 DB Index 가 디스크 영역에 저장되어 있는 데이터에 대한 I/O 요청 횟수를 줄이는 것과 밀접한 영향이 있다는 것을 쉽게 유추할 수 있을 것이다. 지금부터는 본격적으로 Index 구현과 관련한 자료 구조, 인덱스 사용과 관련한 여러 고려 사항에 대해서 알아보자.
[ 그림 3 ]
먼저 소개할 자료 구조는 Hash 알고리즘을 활용한 Hash Table 이다. Hash Table 은 Map 타입이므로 Key : Value 구조를 갖는데, 여기서 Index 가 Key 에 해당하고 Value 가 데이터 또는 데이터를 가리키고 있는 포인터 (논리 또는 물리 주소) 로 볼 수 있다.
우선 Hash Table 자료 구조의 가장 큰 장점은 탐색 과정이 상수(O(1)) 시간에 처리된다는 점이다. 따라서 단 건 조회를 하는 경우 Hash Table 을 사용하는 경우 해당 데이터를 매우 빠르게 탐색할 수 있다는 장점이 있다.
[ 그림 4 ]
[ 그림 5 ]
다만 해시 알고리즘 구조 상 항상 탐색 과정에서 O(1) 을 보장할 수 없다. 이유는 해시 충돌로 인한 문제 때문인데, [ 그림 4 ] 와 같이 Hash Function 의 인풋 값은 무한하지만 반대로 일정한 길이의 값을 갖는 해시 값 (또는 해시 코드)은 유한한 값을 갖게 되므로 결과적으로 [ 그림 5 ] 와 같이 서로 다른 인풋 값의 해시 값이 동일한 해시 충돌 현상이 일어날 수 있다.
해시 충돌이 일어나면 [ 그림 3 ] 의 버킷 내부에서 연결 리스트를 활용해서 해시 코드가 같은 값을 관리할 수 있는데, 이 경우 탐색과 관련한 시간 복잡도가 O(1) -> O(N = 한 버킷에서 관리되는 데이터 수) 이 된다.
Index 에 해시 알고리즘을 기반으로한 해시 테이블 구조를 사용 했을 때 단 건 조회에는 매우 좋은 성능을 가질 것으로 판단할 수 있다.
전방(Prefix) 일치와 같이 값의 일부만 검색하거나 범위를 검색할 때는 해시 인덱스를 사용할 수 없다.
다만 위 인용 내용과 같이 값의 일부만 검색하는 경우 일반적으로 완전히 다른 해시 값을 갖게 되므로 Index 값의 일부분만 활용해 검색할 수 없다는 특징이 있다. 또한 각 Index 가 해시 함수를 거쳐 해시 값을 갖게 되는 구조로 동작하므로 Index 로 활용되는 컬럼에 대해 정렬이 오름 또는 내림차순과 같은 정렬이 적용되지 않은 상태이므로 범위 검색에 있어서 단 건 검색에 비해 상대적으로 비효율적이다. 일반적으로 DBMS 에서 전방 일치 기반 검색 또는 >, >=, <, <= 와 같은 부등호가 포함된 쿼리를 비교적 자주 사용한다는 점에서 DB Index 자료 구조로써 Hash Table 이 주로 사용되기에는 여러 제한이 있다는 것을 이해할 수 있다.
다음 글에서는 DBMS 에서 Index 자료 구조로 주로 사용하는 B-Tree 에 대해서 다룰 예정이다.
Real MySQL 8.0 | 4장 아키텍처 Real MySQL 8.0 | 8장 인덱스 Hash function - Wikipedia mysql 인덱스 정리 및 팁 DB Index 입문