B-Tree

주제

목차

내용

B-Tree (Balanced Tree)

• 인덱스를 이루고 있는 자료구조

• MySQL의 InnoDB는 B+Tree 로 이뤄져있음 ⇒ B-tree의 확장된 개념

MySQL 5.5 버전부터 default 입니다 InnoDB는 트랙잭션 격리수준의 팬텀리드 부정합 문제를 해결했답니다 ^~^

• 최대 M개의 노드를 가질 수 있는 B-tree를 M차 B-Tree 라고 한다.

구조

• Root 노드
• 최상위 노드
• 하위의 브랜치 노드 수 만큼의 Row를 가지고 있음

• Branch 노드
• root 와 leaf의 연결고리
• 하위의 leaf 노드 수 만큼의 Row를 가지고 있음
• 데이터가 적을 경우 root + leaf 만 구성 될 수 있음
• 데이터가 많을 경우 branch 아래에 branch가 추가 될 수 있음

• Leaf 노드
• key와 RowId로 구성되어 있음
• RowId : 해당 테이블 Row를 찾아가기 위한 주소 정보
• Key 순서대로 정렬되어있으며, 이전 이후의 Leaf Node Key를 갖고 있음

• Data Block
• Leaf Node의 RowId가 가리키는 테이블 Row의 실제 저장소

원리

• 탐색은 Root → Branch → Leaf → 디스크 저장소 (인덱스에 없을 경우)
• 수직으로 조건에 만족하는 첫번째 레코드를 찾고
• 리프 노드에서 수평적으로 조건에 맞는 레코드를 찾게 됩니다.
 

특징

• 인덱스의 두번째 컬럼은 첫 번째 컬럼에 의존해서 정렬
• 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 열에서만 의미가 있다.
• 3번째, 4번째 컬럼이 있다면 두번째 컬럼과 마찬가지로 3번째 컬럼은 2번째 컬럼에 의존하고, 4번째 컬럼은 3번째 컬럼에 의존한다.

• 디스크에서 읽는 것은 메모리에서 읽는 것보다 성능이 훨씬 떨어진다.
• 인덱스 성능을 향상시키는 것은 디스크 저장소에 얼마나 덜 접근하게 만드느냐
• 인덱스 Root에서 Leaf까지 오고가는 횟수를 얼마나 줄이느냐

• Range Scan
• where의 between조회, 단일 건이 아닌 조회

• Full Table Scan
• 테이블 전체를 스캔
• Leaf 블록간 링크들을 이용하여 정렬된 순서대로 모든 데이터를 읽어나가는 방식
• 조회 조건의 인덱스가 없을 경우
• 조회 조건의 인덱스가 있으나 변조한 경우
• 조회값이 많을 경우에 효율적