실무에서 조회 기능이 메인인 개발을 진행하다보니 DB Transaction 최적화에 대해 이것 저것 찾아보곤 했다. 우아한 테크 콘서트 리뷰 및 영상을 보며 커버링 인덱스등을 적용하기도 했고 테이블 조인을 진행 했을 때 OR은 Full Scan이라 느리다! 라는 것을 보고는 테이블을 데이터를 조회하며 Application 서비스에서 Merge를 했더니 30% 이상 시간이 단축되는 것을 볼 수 있었다.
그래서 문득 Full Scan, Index-Scan과의 차이점이 궁금했고 Index-Scan에 대해서 찾아보다가 DataBase 엔진에서 Index-Scan은 B- , B+ Tree 알고리즘을 이용한다고 되어 있어 조금 정리해보고자 한다.
1) B-Tree?
B-Tree는 보통 Self Balancing 탐색 트리라고 한다. 우리는 많은 데이터를 메인 메모리에 저장할 수 없다. 키의 숫자가 많으면 많을 수록 디스크에 I/O 하는 시간이 길어지며 B-Tree는 디스크 I/O 시간을 줄이고자 하는 알고리즘이다.
2) B-Tree는 다음과 특징을 가지고 있다.
- 모든 Leaves는 같은 레벨이다.
- B-Tree는 최소한의 차수 t를 정의하며 t의 값은 disk block size를 참조한다.
- 모든 루트 Node는 적어도 t-1 키개의 값들을 가지고 있으며 루트는 적어도 하나의 키값을 가지고 있어야 한다.
- 모든 노드는 적어도 2^t -1 개의 키 값들을 가지고 있어야 한다.
- 자식 노드의 수는 키 값의 +1 이다.
- 노드들의 모든 키 값들은 오름차순이다. 키 k1과 k2 값 사이의 자식들은 k1, k2 사이의 값들을 모두 가지고 있어야 한다.
- B Tree는 내부 노드의 자식의 노드 수가 증가 및 축소로 미리 정해진 범위내에서 변경가능하다.,
- 균형잡인 이진트리와 동일하게 Search, Insert, Delete 복잡도는 log(N)이다.
- B- Tree의 노드 삽입은 리프 노드에서만 가능하다.
B-Tree를 그림 형태로 나타내면 다음과 같다.
3) B-Tree 몇가지 요소
1. 노드 수가 N개이고 노드의 최대 자식수가 M개일 때 B-Tree의 최소 높이는
2. 노드 수가 N개이고 루트가 아닌 노드의 최소 자식수 d개 일 때 B-Tree의 최고 높이는
이며 t값은
4) B-Tree의 순회
B-Tree는 이진트리와 유사하게 순회한다. 가장 왼쪽의 노드들을 탐색한 후 맨 마지막으로 오른쪽 노드들을 탐색한다.
5) B-Tree의 로직
B-Tree는 이진트리와 유사하게 탐색을 진행합니다. 각 레벨에서 키 값이 범위에 있지 않으면 그 키는 다른 브렌치에 있다고 판단합니다. 찾아야 하는 값이 리프노드에 없으면 NULL을 반환합니다.
B-Tree에서 Key값이 130인 것을 탐색해보는 예제를 그림으로 그려보자.
1) RootNode를 탐색한다.
2) 내가 찾으려는 130이 Root Key값 150보다 작으니 왼쪽 자식노드로 이동한다.
3) 해당 노드의 키 최대값 75보다 크므로 자식노드의 Right로 이동한다.
4) 해당 노드에서 130을 리턴한다.
간단히 B-Tree의 특징과 순회방법에 대해서 정리했고
실제적으로 DB 엔진에서 Index Scan시 사용하는 알고리즘은 B-Tree 개념에 일부 추가된 B+Tree 알고리즘이다.
이 다음 포스팅은 B+Tree를 통해 DB 엔진이 어떻게 Index Scan을 하고 있는지 알아보려고 한다.
끝.
'알고리즘 문제 > 기타' 카테고리의 다른 글
| [알고리즘] 순열(Permutation) 및 조합(Combination) 알고리즘 (0) | 2020.08.17 |
|---|
댓글