[Database] B-Tree 인덱스

1. 인덱스란?

B-Tree 인덱스에 대해서 알아보기에 앞서 인덱스에 대해서 간단하게 알아보자. 참고로 이 글은 MySql을 기준으로 작성 되었다.

DB 인덱스는 데이터베이스에서 데이터 검색 속도를 최적화하기 위한 자료 구조이다. 인덱스를 사용하면 전체 테이블을 스캔하는 대신 인덱스를 사용하여 필요한 데이터를 훨씬 더 빠르게 찾을 수 있다. 인덱스의 작동 방식은 책의 색인과 유사하다. 책의 색인에서 특정 주제나 키워드를 찾으면 해당 내용이 있는 페이지 번호가 나열되어 있어, 책의 모든 페이지를 읽지 않고도 원하는 정보를 빠르게 찾을 수 있는 것처럼 인덱스에도 key-value 형식으로 데이터들이 저장 되어있다.

인덱스는 여러가지 기준으로 나눌 수 있는데 그 중 알고리즘에 따라 나누면 대표적으로 다음과 같은 2가지 인덱스가 있다.

• B-Tree 알고리즘 : 가장 일반적으로 사용되는 인덱스 알고리즘으로서, 나온 기간만큼이나 성숙한 인덱스이다. 원본 값을 이용해 인덱싱하는 알고리즘이고, Tree 구조를 이용하는 알고리즘이다. 여기서 B가 "Binary(이진)"으로 알고있는 경우가 많은데, 실제로는 "Balanced"를 의미한다.
• Hash 인덱스 알고리즘 : 칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로, 검색 속도가 O(1)을 자랑한다. 하지만 값을 변형해서 인덱싱하므로 정확하게 일치하는 인덱스에서만 활용이 가능하다는 단점이 있다. Hash 인덱스는 주로 메모리 기반의 데이터베이스에서 많이 사용된다.

이 중에서 가장 많이 사용되는 B-Tree 인덱스 알고리즘에 대해서 알아보자.

2. B-Tree 인덱스 알고리즘

위에서 언급 했듯이 B-Tree 인덱스 알고리즘은 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. Balanced-Tree라고 불리는데, 이는 항상 B-Tree의 주요 원칙이다. B-Tree는 다음과 같은 특징을 가지고 있다.

1. 노드의 키 개수 제한: 각 노드는 최소 ⌈M/2⌉−1개 (M은 트리의 차수)의 키를 가져야 하며, 최대 M-1개의 키를 가질 수 있다.
2. 리프 노드의 깊이 일치: 모든 리프 노드는 동일한 깊이를 가진다. 즉, 루트에서 어떤 리프 노드까지의 경로 길이는 모두 동일하다.
3. 노드의 분할과 병합: 삽입 또는 삭제 연산으로 인해 노드의 키 개수가 원칙을 위반하게 되면, 노드를 분할하거나 병합하여 균형을 유지한다.

이러한 이유로 B-Tree는 항상 균형 잡혀있다라고 표현을 하는 것이다.

2.1 구조

B-Tree의 구조에 대해서 알아보자.

출처 : https://devlog-wjdrbs96.tistory.com/342

B-Tree는 최상위에 하나의 루트 노드가 존재한다. 그 하위에 자식 노드들이 붙어있고, 마지막에 리프 노드가 존재하는 트리구조이다. 리프 노드는 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고있다. 루트 노드와 리프 노드 사이에 존재하는 노드는 브랜치 노드라고 표현한다.

MyIsam 엔진의 경우 리프 노드가 실제 데이터 파일의 주소를 가진다. 하지만 InnoDB 엔진의 경우 리프 노드가 Primary 키를 가지고있다.
InnoDB 엔진을 사용하는 테이블에 Primary key를 설정하는 순간 자동으로 Primary key 인덱스를 생성한다. 더 효율적으로 데이터에 접근하기 위해 모든 InnoDB 엔진의 모든 세컨더리 인덱스는 데이터 레코드를 읽기 위해서 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야한다.

2.2 인덱스 키 INSERT, DELETE, UPDATE

인덱스는 보통 검색을 위한 자료 구조이다. 검색을 빠르게 하는 대신 추가, 삭제, 변경의 속도는 상당히 느려질 수 있다.
- INSERT

새로운 키 값이 테이블에 추가 될 때, 생성 되어있는 인덱스에도 그 값이 추가 되어야한다. B-Tree의 경우 해당 키 값을 바탕으로 저장될 위치의 리프 노드를 찾고 저장한다. 이 때 리프 노드의 페이지가 꽉 찬 경우에는 리프 노드가 분리 되어야한다. B-Tree는 항상 균형을 유지해야하니 리프 노드가 상위 브랜치 노드에 영향을 끼치게 된다. 이러한 이유로 키 추가에 대한 비용이 크다고 볼 수 있다.

- DELETE

B-Tree의 키 삭제는 리프 노드를 찾고 그냥 삭제 마크만 하면 된다. 이렇게 삭제된 공간은 보통 재활용된다.

- UPDATE

인덱스 키 값은 단순히 변경만 되는 것이 아니라, 그 값에 따라 리프 노드의 위치가 달라진다. 그러므로 키 삭제 -> 키 추가의 과정을 다시 거쳐야해서 상당히 비용이 크다.

3. B-Tree 인덱스 키 검색

인덱스는 검색을 위한 자료 구조인 만큼 검색 방법도 다양하고, 제약 사항도 다양하다. 이 중 가장 많이 사용되는 검색 방법을 알아보자.

3.1 인덱스 레인지 스캔

B-tree 인덱스의 레인지 스캔은 인덱스를 사용하여 특정 범위의 값을 선택하는 검색 방법이다. 인덱스 레인지 스캔은 B-tree의 구조상 시작 값에서 종료 값까지의 범위 내의 키 값을 효과적으로 검색할 수 있다.

다음과 같은 쿼리가 있다.

SELECT * 
FROM users 
WHERE age BETWEEN 35 AND 45;

1. 최솟값 35가 30보다 크고 100보다 작다 -> 자식 브랜치 3번 페이지 노드로 이동

2. 3번 페이지의 노드 중 최솟값인 35 발견 -> 리프 6번 페이지 노드로 이동

3. 오름차순으로 정렬되어있으니 위쪽 값 확인 -> 34이므로 35보다 작음 -> 탐색 x

4. 아래 쪽 값에서 40 이하인 값들을 쭉 찾아서 반환

 

만약 인덱스 값(이 경우 age)만 검색하면 여기에서 바로 반환을 한다. 하지만 Primary Key로 실제 데이터 파일의 레코드를 읽어야하는 경우가 있다. 위에서 언급 했듯이 Primary Key의 B-Tree를 타서 실제 물리 주소 값들에 접근한다. 

실제 주소값으로 데이터를 가져오는 작업은 상당히 비용이 많이드는 작업이다. 데이터를 많이 가져오는 경우에는 풀 스캔이 더 효과적인 경우도 있다. 
그래서 인덱스를 통해 읽어야 할 데이터 레코드가 전체 레코드의 20% ~ 25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 된다.

3.2 루스 인덱스 스캔

앞선 인덱스 레인지 스캔은 "타이트 인덱스 스캔"으로 분류가 된다. 루스 인덱스 스캔은 반대로 듬성듬성 인덱스를 읽으면서 성능을 최적화 하는 방법이다.

다음과 같은 쿼리가 있다고 하자.

SELECT age, MIN(emp_no)
FROM emp
WHERE age BETWEEN 35 AND 37
GROUP BY age;

이 쿼리에서 사용된 emp 테이블은 (age, emp_no) 두 칼럼으로 이루어진 다중 컬럼 인덱스가 있다. 

둘 다 오름차순으로 정렬이 되어있어서 그림과 같이 첫번째 값을 찾은 후 바로 다음 페이지로 가서 다른 값을 찾을 수 있다.

굳이 아래에 있는 값들을 전부 조건에 맞는지 비교하지 않고 확실한 부분을 생략하는 것이다.

 

루스 인덱스 스캔는 보통 GROUP BY를 사용하는 쿼리에서 자주 사용된다.

 

4. B-Tree 인덱스 사용에 영향을 미치는 요소

B-Tree 인덱스 사용에 영향을 미치는 요소는 여러가지가 있지만 제일 많은 영향을 끼치는 것은 키 값의 크기이다. 

InnoDB 페이지 크기의 기본값은 16KB이다. 이 크기는 따로 설정하지 않는 이상 바뀌지 않는다. 이 말은 키 값의 크기가 작으면 한 페이지에 많은 레코드가 들어가고 크면 많이 들어가지 않는다는 것을 의미한다. 

만약 한 페이지에 600개의 레코드가 들어간다고 가정하자. 이 때 특정 SELECT 쿼리가 레코드 500개를 읽어야한다면 페이지 1개로 끝날 것이다. 하지만 한페이지에 300개의 레코드가 들어가있다면 두개의 페이지를 읽어야한다. 

결국 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.

 

또한 인덱스의 페이지에 적은 레코드가 들어가게 되면 B-Tree의 깊이도 늘어나게 된다.

만약 한 페이지의 레코드가 600개 들어간다면 3 depth에 들어갈 수 있는 최대 레코드 수는 (600 * 600 * 600) 약 2억개이다.

한 페이지에 레코드가 300개 들어간다면 3 depth에 들어갈 수 있는 최대 레코드 수는 (300 * 300 * 300) 약 3천만개이다.
이 경우 한 뎁스를 더 들어가야하는 경우가 많이 발생한다. 이는 디스크를 그만큼 더 읽어야함을 뜻하고 성능이 엄청난 영향을 미친다.