B-Tree, B+Tree

B-Tree(Balanced Tree)

• 자식 2개 만을 갖는 이진 트리를 확장하여 N개의 자식을 가질 수 있도록 고안된 것.
• 좌우 자식 간의 균형이 맞지 않을 경우에는 매우 비효율적이라, 항상 균형을 맞춘다는 점에서 균형 트리라고 불린다.
• 최상위에는 단 하나의 노드 존재 = 루트 노드, 중간 노드를 브랜치 노드, 최하위 노드를 리프 노드라고 한다.

 

Page

• 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 작업 단위.
• 일반적인 인덱스를 포함해 PK와 테이블 등은 모두 페이지 단위로 관리된다.
• 따라서 만약 쿼리를 통해 1개의 레코드를 읽고 싶더라도 결국은 하나의 블록을 읽어야 하는 것이다.
• 그래서 페이지에 저장되는 개별 데이터의 크기를 최대한 작게 하여, 1개의 페이지에 많은 데이터들을 저장할 수 있도록 하는 것이 상당히 중요하다. 
• 페이지에 저장되는 데이터의 크기가 크다면?
  • 디스크 I/O가 많아질 수 있음
  • 메모리에 캐싱할 수 있는 페이지의 수가 줄어들 수 있음
•  DB 성능 개선 혹은 쿼리 튜닝은 디스크 I/O 자체를 줄이는 것이 핵심인 경우가 많다.

 

인덱스는 페이지 단위로 저장되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지한다. 정렬된 인덱스 키를 따라서 리프 노드에 도달하면 (인덱스, 키, PK) 쌍으로 저장되어 있다.

 

 

 

 

• MYSQL은 B+TREE로 인덱스가 구현되어 있다.
• B+TREE는 인덱스 세트와 순차 세트라는 2가지 세트를 만든다.
• 인덱스 세트는 배ㅜ 노드로, 리프에 있는 키들에 대한 경로만 제공한다.
• 모든 키 값은 순차 세트(리프 노드)에 있다.
• 인덱스 세트는 직접 탐색을 지원하며, 순차 세트는 순차 탐색을 지원한다.
• B+TREE는 B-TREE와 다르게 BEST도, WORST도 없다. 탐색은 무조건 O(log N)이다.

 

인덱스의 종류

• 클러스터 인덱스
  • 클러스터링이란, 특성이 유사한 것끼리 모아두는 것.
  • 클러스터 인덱스는 레코드들의 물리적인 저장 순서가 인덱스 순서와 동일하게 되도록 구성한 인덱스다.
  • 인덱스의 리프 노드가 곧 데이터 레코드로, 쉽게 말하면 인덱스 파일과 데이터 파일이 같은 파일로 존재한다.
  • 데이터들을 물리적으로 같은 트랙, 같은 실린더에 배치한다면 탐구 시간이 감소시켜 속도를 높일 수 있다.
  • 사전과 유사하다. 비슷한 영단어는 비슷한 위치에 있다. 그리고 영단어를 찾아보면 데이터도 같이 있다. 이게 바로 클러스터 인덱스이다.
  • 클러스터 인덱스는 보조 인덱스보다 검색 속도가 더 빠르다. 동일하거나 인접한 키 값을 가진 레코드들을 물리적으로도 인접하게 저장하기 때문이다.
  • 단, 데이터의 입력/수정/삭제는 보조 인덱스보다 느리다. 분할을 할 가능성이 높기 때문.
  • 클러스터 인덱스는 여러 개 만들 수 없다. 만약 학번이라는 속성으로 클러스터 인덱스를 B+TREE로 만들었는데, 이름으로 또 물리적인 인덱스를 만들 수 있나? 없다. 데이터를 물리적으로 또 어떻게 저장하라는 건가.
  • 일반적으로 클러스터 인덱스는 PK(기본키)로 만든다.
  • 테이블 생성 시 기본키에 대해 클러스터 인덱스를 자동으로 생성한다.
  • 기본 키를 지정하지 않으면 처음 나오는 UNIQUE 속성에 대해 인덱스를 생성한다.
• 보조 인덱스
  • 클러스터 인덱스가 아닌 모든 인덱스를 가리킨다.
  • 책 뒤의 <색인>과 비슷하다. 원하는 만큼 여러 개를 만들 수 있다.
  • 인덱스 파일만 수정하면 되기 때문에, 클러스터 인덱스보다 입력, 수정, 삭제가 더 빠를 수 있다.
  • 단, 검색 속도는 더 느리다. 인덱스 파일을 찾은 다음에 주소로 가서 데이터 파일을 읽어야 하니까 더 느릴 수 밖에 없다.
  • 보조 인덱스와 클러스터 인덱스 동시 사용
    1. 보조 인덱스를 검색하여 PK 속성 값을 찾고
    2. 클러스터 인덱스에서 해당 레코드를 검색한다.
    3. 실제로 MYSQL 사용할 때는 이런 방법(SELECT와 WHERE절을 이용하여)으로 값을 찾아가기도 한다.

 

인덱스 사용의 장점과 단점

장점 : 인덱스된 속성에 대한 질의를 처리할 때 대상이 되는 데이터 양이 줄어들어 처리속도가 힙 파일보다 빠르다.

단점 : 클러스터 인덱스에서 삽입이 자주 사용되는 경우 부하가 크다.

인덱스는 모든 속성에 대해 만들어 놓지 말고 WHERE, JOIN 절에 자주 사용되는 속성에 만들어주자.