Mysql B-Tree Index

B-Tree 인덱스

모든 값을 순서대로 저장한다. 각 리프 페이지는 루트에서 같은 거리만큼 떨어져 있다. 속도는 트리의 depth 에 좌우된다. ( depth 를 줄이는 방법으로는 브랜치 블록 노드에 저장하는 key 값의 수를 늘리는 방법이 있다. )

• MyISAM
  • 인덱스를 작게 만드는 프리픽스 압축 기법을 사용
• InnoDB
  • 인덱스를 압축하지 않는다.
  • 기본키 값을 이용해서 인덱스된 행을 참조한다.
  • B+트리 구조를 사용한다.

B-Tree 구조

트리의 생성과정

1. 테이블 데이타 정렬
2. 정렬 결과를 리프 블록에 기록하기 시작
3. 리프 블록이 PCTFREE 에 도달하면, 브랜치 블록을 생성하고 리프 블록의 정보를 기록한다.
4. 브랜치 블록이 PCTFREE 에 도달하면, 루트블록을 생성하고 브랜치 블록의 정보를 기록하고, 새로운 브랜치 블록을 생성한다.
5. 새로운 브랜치 블록이 생길 때마다, 루트 블록에 기록한다.

트리에 인덱스 값 추가시

• PCTFREE 에 도달한 경우에는 새로운 블록을 생성하여 등록한다. 새로운 블록을 생성하였으나 더이상 해당 블록에 값이 안 들어올 경우 공간의 낭비가 발생한다.

인덱스 값 삭제시

• 트리내의 로우에 삭제 표시만 한다.

인덱스 값 갱신시

• 인덱스 삭제 과정과 삽입 과정이 순차적으로 발생한다.

PCTFREE : 인덱스 엔트리를 수용하기 위해, 각 블록에 예약된 공간의 총량

B+Tree 구조

B-Tree 와 달리 트리의 최하위 레벨의 리프 노드에만 데이타가 정렬되어 있다. ( 해당 리프 노드는 양방향 링크드 리스트를 사용하여 데이타를 저장한다. )