1. 인덱스가 필요한 이유
실제 데이터가 몇백만/몇천만건이라고 가정해보자.
우리가 실제로 다루는 데이터의 양은 방대하므로 쿼리를 어떻게 작성하냐에 따라
몇천건의 데이터와 다루는것과 다르게 느려질 수도 있고,
비용과 직접적으로 연관될 수 있다.
때문에 인덱스는 비용/속도측면에서 고려해야 할 중요한 기술이다.
느린이유: 풀 테이블 스캔 (Full Table Scan)
인덱스가 없는 테이블에서 특정 데이터를 찾는 것은
100만페이지의 책에서 특정단어를 찾기위해 처음페이지부터 끝페이지까지 1장씩
넘겨서 확인하는 것과 같다.
이러한 작업방식을 Full Table Scan(풀 테이블 스캔)이라고 한다.
풀 테이블 스캔은 빅오표기법으로 O(n)의 시간복잡도를 가진다.
따라서 데이터가 많아질수록 우리 서비스의 검색시간은 정비례하여 늘어나게 된다.
찾아보기(색인)페이지로 풀 테이블 스캔을 피해보자
100만페이지 책에서 특정단어를 찾기위해서 우리는 찾아보기(색인)페이지를 이용한다.
찾아보기 페이지에는
- 키워드가 가나다/알파벳순으로 정렬되어 있거나
- 키워드 옆에는 몇페이지 번호가 적혀져 있다.
데이터베이스의 인덱스(INDEX)는 위와같은 역할을 한다.
- 인덱스는 지정된 컬럼의 값과 실제 데이터행의 위치를 한쌍으로 저장되어 있고
- 인덱스 내부데이터는 항상 정렬되어 있다.
2. 인덱스는 ()를 확장한 자료구조이다.
( )에 들어갈 말은 "이진 탐색 트리(Binary-Search-Tree)"이다.
이진탐색트리는 '왼쪽은 작고 오른쪽은 크다'는 규칙을 따르는 정렬된 이진 트리이다.
이진탐색트리 계산의 핵심은 "한 번에 절반을 날린다"는 것이다.
예를들어, 16개의 데이터가 있다고 가정해보자.
- 16개 데이터가 있다. 루트데이터와 비교하여 절반을 날릴 수 있다. 16 / 2 = 8이다.
- 8개의 데이터가 있다. 비교를 통해 절반을 날릴 수 있다. 8 / 2 = 4이다.
- 4개의 데이터가 있다. 비교를 통해 절반을 날릴 수 있다. 4 / 2 = 2이다.
- 2개의 데이터가 있다. 비교를 통해 절반을 날릴 수 있다. 2/ 2 = 1이다.
- 1개의 데이터 값이 맞는지 확인한다.
우리는 원하는 값을 16개의 데이터 중에서 4번만에 찾게 되었다.
이진탐색트리는 빅오 표기법으로 O(log₂n)인데,
풀테이블스캔이 O(n)인것과 확연한 속도차이가 있다.
16개를 4번 비교만에 찾을 수 있다.
16개의 데이터를 4번의 비교만으로 최종 값으로 도달할 수 있다.
- 2개의 데이터 2로 1번 나누기,
log₂(2)=1 - 4개의 데이터 2로 2번 나누기,
log₂(4)=2 - 8개의 데이터 2로 3번 나누기,
log₂(8)=3 - 16개의 데이터 2로 4번 나누기,
log₂(16)=4 - 32개의 데이터 2로 5번 나누기,
log₂(32)=5 - 64개의 데이터 2로 6번 나누기,
log₂(64)=6
... - 1024개의 데이터 2로 10번 나누기,
log₂(1024)=10 - 16,384개의 데이터 2로 14번 나누기,
log₂ (16384)=14 - 65,536개의 데이터 2로 16번 나누기,
log₂ (65536)=16 - 131,072개의 데이터 2로 17번 나누기,
log₂ (131072)=17 - 1,000,000개의 데이터 2로 약 20번 나누기,
log₂ (1,000,000)≈19.93 - 10,000,000개의 데이터 2로 약 24번 나누기,
log₂ (10,000,000)≈23.22 - 100,000,000개의 데이터 2로 약 27번 나누기,
log₂ (100,000,000)≈26.57
따라서 우리는 정렬이 되어 있는 인덱스로
1억개의 데이터중에 26.57번만에 원하는 데이터를 찾을 수 있다는 것이다!
다시 한번 말하지만, 이진탐색트리는 "데이터의 값을 기준으로 정렬해서 저장하고 있다는 것이다.
3. 보완: 밸런스 트리 (Balanced Tree)
이진탐색트리가 균형이 맞지 않는다면 최악의 경우
풀 테이블 스캔과 같은 O(n)의 성능을 낼 수도 있다.
예시를 봐보자.
- 5개의 데이터가 모두 오른쪽으로 치우쳐져있다.
- 15라는 데이터를 찾기위해서는 5번의 검색이 필요하다.
- 이 경우에는 성능상 풀 테이블 스캔과 같다.
O(n)
이때, 동적으로 깨진 이진탐색트리의 균형을 맞춘다.
- 중간값인 6을 기준으로 다시 이진탐색트리를 정렬한다.
- 이렇게 균형을 유지하는 것을 밸런스 트리(Balanced Tree)라고 한다.
- 대부분의 RDBMS에서는 인덱스에 B-Tree를 사용해 균형을 유지하므로,
최악의 경우에도O(log₂n)의 성능이 나온다.
밸런스 트리의 한 종류: B-Tree
B-Tree는 밸런스 트리(Balaned Tree)에 속하며,
대부분의 관계형데이터베이스(RDBMS)에서 B-트리/B+트리를 사용하고 있다.
1. B-트리는 자녀노드의 최대개수를 늘릴 수 있다.
- 이진탐색트리는 자식노드를 최대 2개밖에 가질 수 없었다.
때문에 데이터 검색 시 많은 비용이 들어갈 수 밖에 없다. - 하지만 그림처럼 부모노드에 50과 80이 존재한다면,
자식노드를 3개나 가질 수 있다.
2. B-트리는 아래와 같은 특징을 갖게 된다.
- 부모노드에 2개 이상의 Key가 존재하며, 항상 정렬되어 있다.
- 각 노드에는 각 Key에 대응하는 Data도 함께 갖고 있다.
- 정렬된 순서에 따라 자녀노드들의 범위가 결정된다.
- 각 노드의 최대 자녀노드 수를 M이라고 할 때, M차 B-트리라고 한다.
(ex. 그림은 최대 3개 자녀노드를 가질 수 있기 때문에 3차 B-트리이다.)
3. B-트리는 대용량 데이터를 다루는 환경에 최적화되어 있다.
- DB는 데이터를 메모리가 아닌 디스크에 저장한다.
- 디스크에서 데이터를 읽는 작업(Disk I/O)은 메모리에서 읽는 것보다 훨씬 느리다.
- 따라서 디스크 I/O 횟수를 줄이는 것이 성능에 많은 영향을 미친다.
- 이진탐색트리는 한 노드가 하나의 데이터만 갖고있기 때문에,
데이터를 검색할 때 여러노드를 방문할 경우 많은 블록(block)을 읽어야 한다.block: 데이터를 읽고 쓰는 단위 (4KB, 8KB, 16KB 등이 있음)
- 반면, B-트리는 하나의 노드가 여러개의 자식노드를 가질 수 있기 때문에
디스크에서 한번 읽을 때 더 많은 정보를 가져올 수 있다. - 따라서 B-트리는 디스크 I/O 횟수를 최소화하면서 대용량데이터에서 효율적인 검색성능을 제공한다.
다른 밸런스 트리는 채택되지 않은 이유 (AVL, Red-Black)
그림과 같이 평균/최악의 경우가 AVL-트리나 Red-Black 트리와 같은데,
왜 데이터베이스 인덱스는 B-트리 계열을 채택했을까?
1. 컴퓨터 구조를 파악해보자
- DB 데이터는 디스크(HDD/SDD)에 영구적으로 저장된다.
- 핵심이 되는 데이터 + 자주 쓰이는 데이터는 RAM에 올라가지만
그렇지 않은 대부분의 데이터들은 디스크에 위치한다. - 디스크는 데이터를 효율적으로 읽고 쓰기위해 블록단위로 읽고 쓴다.
block: 데이터를 읽고 쓰는 단위 (4KB, 8KB, 16KB 등이 있음)
- 따라서 DB는 데이터를 조회할 때, 디스크에 최대한 적게 접근하는 것이
성능면에서 좋다. - 또, 블록단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장해놓으면
더 효율적이다.
2. AVL, Red-Balck 트리는 "이진탐색트리"이다.
- 이진탐색트리는 자녀노드 수가 최대 2개이므로 최대 1/2로 탐색범위를 줄일 수 있다.
- 하지만 B-트리는 M의 개수에 따라 1/3 혹은 1/5까지 탐색범위를 줄일 수 있다.
- 데이터를 찾을 때 탐색범위를 줄인다는 것은 "디스크 접근이 최소화"된다는 것이다.
- 또한 B-트리의 경우, 연속된 데이터가 연관되어 있는 데이터이기 때문에
블록단위로 읽고 쓰는 과정에서도 더욱 효율적이다.
❓ 해시테이블은 인덱스로 사용할 수 없나요?
ㅇㅋ.
다른 밸런스 트리는 왜 채택되지 않았는지 알았다.
그렇다면 가장 빠른 해시테이블은 왜 인덱스로 채택되지 않았을까?
해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근을 하기 때문에 O(1)이라는 시간 복잡도를 가진다.
그러나 이는 온전히 '단 하나의 데이터를 탐색하는 시간' 에만 O(1)이다.
우리는 DB에서 등호(=) 뿐 아니라 부등호(<, >)도 사용할 수 있다.
또한 모든 값이 정렬되어있지 않으므로,
해시 테이블에서는 특정 기준보다 크거나 작은 값을 찾을 수 없다.
찾을 수 있다고 해도 O(1)를 보장하기 어렵다.
❓ 배열은 인덱스로 사용할 수 없을까?
- 배열은 데이터가 메모리상 차례대로 저장되어 있어 B-트리보다 탐색이 빠르다.
- 해시테이블과 다르게 정렬될 수 있기 때문에 부등호 연산에도 문제 없다.
- 하지만 배열이 B-트리보다 빠른것은 탐색뿐이다.
배열에서 삽입/삭제가 일어나는 경우!
- 새롭게 삽입되는 데이터가 가장 큰 데이터라서
바로 맨 뒤에 저장된다면O(logN)이 걸리겠지만 - 최악의 경우인 가장 작은 데이터라면 자리 탐색 시간인 O(logN)과
맨 앞에 새로운 데이터 삽입을 위해 모든 데이터를 한 칸씩 뒤로 이동하는 시간 O(N)으로, 하나의 요소에 대한 삽입,삭제는 O(N+logN) =O(N)의 시간이 걸리게 된다.
✨ 어인B (어차피 인덱스는 B-트리)
결론적으로 DB 인덱스로 B-트리 가장 적합한 이유들을 정리하면 아래와 같다.
- 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
- 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
- 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
4. 추가: B-트리를 확장한 B+트리
우리가 자주 사용하는 MySQL의 InnoDB 스토리지 엔진은 주로 B+ Tree를 사용한다고 한다.
간단한 개념만 알고 넘어가자!
- B+트리는 B-트리의 확장개념으로, B-트리의 경우, key와 data를 담을 수 있다.
- 하지만, B+트리의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다.
- 오직 리프 노드(마지막 계층 노드)에만 key와 data를 저장하고,
리프 노드끼리Linked list로 연결되어 있다.
B+트리의 장점
-
리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다. (cache hit를 높일 수 있음)
-
풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.
출처
[쉬운코드] B tree의 개념과 특징
[쉬운코드] B tree는 왜 DB 인덱스로 사용될까
데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가
B-트리, B+트리란?
