[Real MySQL 1권] B-Tree - 구조 및 특성, 키 추가 및 삭제

 

 

1) B-Tree란? 

 

- B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 

  하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다.

  B-Tree에는 여러 가지 변형된 형태의 알고리즘이 있는데, 일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree

  가 사용된다.

 

- B-Tree의 가장 중요한 특징은 다음 2가지이다. 

  (1) 칼럼의 원래 값을 변형시키지 않음

 - 이 특징 덕분에 전방(Prefix) 일치나 값의 일부만 검색하는 것이 가능다.

 

  (2) 인덱스 구조체 내에서 항상 정렬된 상태로 유지 

 - 이 특징 덕분에 특정 값을 찾을 때, 탐색이 O(logn) 의 시간 복잡도로 가능하다.

 

- 이러한 특징들로 인해,  대부분의 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다. 

 

2) B-Tree의 구조 및 특성

 

- B-Tree 인덱스를 제대로 사용하려면 B-Tree의 기본적인 구조를 알아야 한다.

  B-Tree는 트리 구조의 최상위에 하나의 "루트 노드(Root node)"가 존재한다.

  그리고 그 하위에 자식 노드가 붙어 있는 형태다. 

 

- 트리 구조의 가장 하위에 있는 노드를 "리프 노드(Leaf node)"라 하고,

  트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 "브랜치 노드(Branch node)"라고 한다.  

 

- 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데,

  인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다. 

  아래 그림은 B-Tree 인덱스의 각 노드와 데이터 파일의 관계를 표현한 것이다. 

 

 

- 여기서 주의할 점은 인덱스의 키 값은 모두 정렬돼 있지만,

  데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다는 점이다.. 

  많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않다

 

 

3) B-Tree 인덱스 키 추가 및 삭제 

- 테이블의 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생한다.

  인덱스 키 추가나 삭제가 어떻게 처리되는지 알아두면 쿼리의 성능을 쉽게 예측할 수 있을 것이다. 

  또한 인덱스를 사용하면서 주의해야 할 사항도 함께 살펴보겠다. 

 

 

(1) 인덱스 키 추가

- 일반적으로 테이블에 인덱스가 3개(테이블의 모든 인덱스가 B-Tree라는 가정하에)가 있다면 

  이 때 테이블에 인덱스가 하나도 없는 경우는 작업 비용이 1이고, 

  3개인 경우에는 5.5 정도의 비용(1.5*3+1) 정도로 예측한다. 

 

- 중요한 것은 이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라

  디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이라는 점이다. 

 

 

(2) 인덱스 키 삭제

- B-Tree의 키 값이 삭제되는 경우는 상당히 간단하다.

  해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 

  이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

 

4) B-Tree 인덱스 키 검색

- INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서

  인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다.

  인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐

  최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 

  이 과정을 "트리 탐색"이라고 한다. 

 

- 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE나 DELETE를 처리하기 위해

  항상 해당 레코드를 먼저 검색해야 할 경우에도 사용된다. 

   B-Tree 인덱스를 이용한 검색은 100% 일치 또는

   값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있다. 

 

 

5) InnoDB 스토리지 엔진에서 인덱스의 중요성 

-  InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있다. 

   InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이

   검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다.

   

- 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면

  불필요하게 많은 레코드를 잠근다. 

   지어 테이블의 모든 레코드를 잠글 수도 있다.

   InnoDB 스토리지 엔진에서는 그만큼 인덱스의 설계가 중요하고 많은 부분에 영향을 미친다.