🌳 인덱스의 자료구조 균형트리(B-Tree)

균형트리는 나무를 거꾸로 표현한 자료구조로 트리에서 제일 상단의 뿌리를 루트, 줄기를 중간 ,끝에달린 잎을 리프라고 부릅니다.

🌴 B트리의 개념

데이터가 저장되는 공간을 노드라고 합니다. 이 노드는 mysql에서는 페이지라고 부릅니다.

• 균형트리(B 트리)는 무조건 루트 페이지부터 검색합니다.

• MMM을 찾는 다고 가정할 시 루트 페이지의 AAA, FFF, LLL을 읽은후 세번째 리프 페이지로 이동하여 MMM을 찾습니다.

• 이런 과정은 데이터를 처음부터 끝까지 검색하는 전체 테이블 검색에 비해 적은 페이지를 읽을 수 있습니다.

• 데이터가 훨씬 많은 경우에서는 균형 트리 구성여부에따라 읽어야하는 페이지 수의 차이가 굉장히 큽니다.

🌲 균형 트리의 페이지 분할

앞서 균형트리를 사용하여 효울적인 부분을 살펴보았습니다.

이전에 데이터 변경작업 시 성능이 나빠질수있다고 하였는데, 특히 INSERT작업이 진행될경우 더 느리게 발생합니다.

그 이유는 페이지 분할이라는 작업때문입니다.

만약 위 사진과 같이 리프페이지에 한자리의 칸이 존재한다면, 새로운 자료를 나머지 자료에 삽입하면됩니다.

하지만 리프페이지에 자리가 꽉찼고 새로운 자료가 추가되어야한다면?

GGG를 추가한다고 한다면, 가득찬 두번째 리프페이지를 적당히 순서대로 나누어서 새로운 페이지를 만들어서 분할을 하게됩니다.

이것이 페이지 분할입니다. 그렇게 페이지분할로인해 생겨난 여분의 자리에 GGG를 추가합니다.

그리고 새로운 페이지를 루트페이지에 추가합니다.

🏝 위 페이지의 상태에서 다시 PPP,QQQ를 추가한다면?

• 네번째 리프 페이지에 PPP를 추가하고나서 QQQ를 추가하면 이미 페이지가 가득차서 페이지 분할을 진행해야합니다.

• 네번째 리프페이지에서 페이지분할을 진행하고나니 루트페이지가 가득차있음을 깨닫고 루트페이지를 페이지 분할합니다.

• 루트의 페이지 분할로 중간노드가 생성되고 그로인해 새로운 루트가생성되어 위와같은 상태로 변합니다.

• 결국 QQQ 로인해 3개의 새로운 페이지와 2회의 페이지 분할이 진행되었습니다.

이를 통해 데이터 변경이 작업이 왜느려지는지 알수 있습니다.

🌴 인덱스에서 데이터 검색하기

1. spc를 찾고자한다. 먼저 루트페이지를 탐색한다.

2. mmu < spc < twc 이므로 mmu를 타고 리프페이지로 이동한다.

3. 리프페이지에서 spc를 찾고 데이터가 우주소녀임을 알아낸다.

요약

• 전체 테이블 검색 : 데이터를 처음부터 끝까지 검색, 인덱스가 없으면 이 수 밖에없음

• 페이지 분할 : 데이터를 입력 시, 입력할 페이지에 공간이없어서 2개 페이지로 데이터를 나누는 것

✅ 참고

혼자 공부하는 sql
http://www.yes24.com/Product/Goods/104661489