[데이버테이스] 번외편) B-Tree 인덱스

1. B-Tree 인덱스
   출처: https://helloinyong.tistory.com/296
   
   여기서 B를 흔히들 많이 알고 있는 Binary로 오해하는 경우가 많다. 하지만, B는 Balanced Tree로 트리가 한쪽으로 편향되지 않게 노드 삽입 및 삭제시 규칙에 따라 트리가 재정렬되어 루트 노드를 기준으로 좌우 서브 트리가 균형을 유지하는 트리를 의미한다.

• 최상위 노드를 루트 노드라고 하고, 가장 하위에 있는 노드를 리프 노드, 그 중간에 있는 노드들을 브랜치 노드라고 한다.

Q) 일반적인 Tree를 사용하면은 아래와 같이 한쪽으로 편향되어서,안쓰는 건 알겠는데 Hash 자료구조가 시간복잡도 O(1)로 가장 성능이 좋을텐데 왜 굳이 B-Tree를 쓰나요?


A) 쿼리문을 날릴 때, 특정 값으로만 데이터를 가져오는 것이 아니라 범위 내에 있는 값을 가지는 데이터들을 조회하는 경우 가 있기 때문이다. 만약 모든 쿼리가 아래와 같다면 해쉬 자료구조를 활용한 인덱스 방식이 효율적일지도 모른다.

Select eid from Employee where eid = 1;

하지만, 일반적으로는 아래와 같이 특정 값들의 범위내에 있는 데이터들을 조회하는 경우도 빈번하다. (role -> 0= 사원, 1 = 과장, 2= 사장, etc)

Select eid, role where role >= 1;

결론은 최악의 시간복잡도도 O(logn)을 보장해주고, 규칙에 따라 트리 내 모든 데이터가 항상 정렬된 상태로 유지되며, 부등호 연산 처리도 능한 B-Tree를 사용한다.

내용을 정리하면서, 학부시절에 학습했던 Balanced Tree의 한 종류인 red-black Tree가 생각나서 이 자료구조도 RDBMS의 인덱스 방식으로 쓰이는지 궁금해졌다.

-> 답을 먼저 말하자면 NO이다.


red-black tree의 특징 대해 간단하게 정리해보았다.

출처: https://www.javatpoint.com/red-black-tree-java

특징

• 그림처럼 각 노드에 하나의 데이터만 가진 상태로 좌우 SubTree의 균형을 유지한다.
• 빨간색과 검은색 노드로 구분지어 노드의 삽입 및 삭제시 노드들을 재정렬하여 균형을 유지한다.
• 루트 노드는 항상 검은색이다.
• 빨간색 노드의 자식은 모두 검은색이다.
• 어떤 노드로부터 시작하여 모든 리프 노드에 도달하는 경로에는 동일

red-black tree가 인덱스 방식으로 사용되지 못한 이유

• red-black tree는 하나의 노드 내에 무조건 하나의 데이터만을, B-Tree는 하나의 노드 내에 여러 데이터를 저장할 수 있다는 점 에서 데이터 탐색 시 속도 차이가 크다.
  -> RedBlack-Tree의 구조를 보면 하나의 노드에 하나의 데이터만 있기 때문에 자식 노드로 넘어가는 횟수가 많을 것이고, 그러한 노드와 노드 사이는 데이터가 저장되어 있는 주소를 가리키는 참조 포인터로 연결되어 있다. 하지만 B-Tree의 경우, 하나의 노드 내에 정렬된 데이터들이 배열의 모습을 띄고 있는데 실제 메모리 상에 배열처럼 차례대로 저장이 되어있다.

배열의 인덱스 기반 데이터 접근이 포인터 기반 접근 방식보다 훨씬 빠르다!

B-Tree 기반 인덱스의 동작 방식

출처: Real MySQL

데이터베이스에서는 인덱스와 실제 데이터가 저장된 데이터는 따로 관리하고, 실제 데이터를 찾아가기 위해서는 인덱스의 리프노드에 있는 주솟값을 활용해야 한다. 아래는 InnoDB 테이블에서 인덱스를 통해 레코드를 읽는 과정을 나타낸 사진이다.

출처: Real MySQL

인덱스 전용 B-Tree의 리프노드의 프라이머리 키 값을 일종의 주소로 사용하여 프라이머리 키 인덱스 B-Tree에서 해당 레코드를 찾아가는 과정이다.

지난 블로그 글을 읽고 남겨준 질문

(1) 필드가 boolean 타입일 때 인덱싱이 의미가 없다고 했는데 왜 그런가요?

• 테이블의 컬럼이 가질 수 있는 Unique한 값의 개수를 카디널리티라고 하는데, 제가 생각하기에 카디널리티가 클수록 인덱싱을 거는게 적절하다고 생각합니다. 만약에 Boolean같은 카디널리티가 2인 필드에만 인덱싱이 걸려있다면, 두 그룹으로 분리되어 있을텐데 이런 것보다는 PK나 고유한 값 같은 카디널리티가 로우 수에 가까운 필드에 걸면은 인덱싱을 걸 때 더 좋은 성능을 보일 것이라고 생각해요.

(1-1) 혹시 boolean에서 인덱스를 할 때와 안 할 때 시간이 얼마나 차이 나는지도 확인해보셨었나요? boolean보다 값의 범위가 넓을 때는 많이 차이 나나요?

• 실무에서 로우가 수천개에서 수만개정도 되는 데이터 필드중에 하나가 boolean 타입이었는데 인덱싱을 걸었을 때와 걸지 않았을 때의 차이가 크지는 않았습니다! 정확히 수치화하지는 못했지만, 인덱싱이 적용된 필드를 가지는 엔티티에 새로운 로우를 쌓을 때, 적용되지 않았을 때보다 성능이 좋지 못하다고 생각해서 인덱싱을 적절히 활용해야 조회 / 다른 DML 쿼리의 성능을 둘다 좋게 가져갈 수 있지 않을까 싶습니다.

-> 추후에 실제로 어느 정도의 성능 차이가 있는지 임의로 데이터를 넣어두고 확인해보고 블로그 글로 기록해보려고 한다. 값진 질문 및 피드백 주신 분들 다들 감사드립니다!

인덱스 부분을 두 개의 글로 나누어 정리했는데도,, 아직 다 정리하지 못한 것 같다.. 책을 읽고 더 깊이있게 이해하고 나서 글 하나 더 작성해서 인덱스 내용 정리를 마무리하고자 한다.