06-02 균형트리

아래의 상기 내용은

"혼자공부하는 SQL"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.균형트리(B-tree)

 1)정의

  노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리.

 2)개요 및 개념

  -클러스터 인덱스와 보조 인덱스는 내부적으로 균형트리라는 자료구조에 나오는 데이터 구조이다.

  -마치 나무를 거꾸로 한 듯한 같이 뿌리,줄기, 잎 같이 각각의 계층을 표현하고 있다.

 

 -데이터가 저장되는 곳을 노드(node)라고 부르며 위의 그림은 총 4개(루트 1개 리프 3개)가 있다.

  -MySQL에서는 페이지(Page)라는 명칭을 쓴다.

  -페이지는(page)는 최소한의 저장단위로 16kbyte의 크기를 가지며 1개의 데이터만 입력해도  16kbyte의 크기가 필요하다.

3)데이터 검색 비교

 -균형트리는 데이터를 검색할 때 뛰어난 성능을 지닌다.

  -일반적으로 데이터를 검색할 때 페이지의 조회 개수가 적은 것이 효율적이다.

 

  -트리가 아닌 구조는 총 3 페이지의 노드를 검색한다.

 -트리 구조는 루트 페이지 리프 페이지 총 2개를 검색하여 효율적이다.

4)페이지 분할

 -트리는 검색에는 빠르지만 데이터를 변경 작업(삽입,삭제,변경)같은 작업은 성능이 나빠진다.

 -페이지 분할이 데이터를 나누는 작업.

 -데이터가 변경작업이 일어 났을 때 균형트리의 정렬 및 노드 생성 및 분할 같은 작업이 일어나 추가적인 작업시간이 필요로 하게 되어 성능에 악역향을 주는 것이다.

2.실습: 클러스터형 인덱스와 보조 인덱스 생성 및 데이터 검색

 1)클러스터 인덱스

 

 

 

 2)보조 인덱스