지난 시간에는 B-Tree의 구조까지 보았는데 이번에는 안에 있는 의미를 파악해 보겠습니다 해당 쿼리는 다음 같고 인덱스는 다음 같이 설정되어 있습니다
1
2
3
4
create index custom_N1 on custom(customName)
Select * From custom where customName = '이재희'
Root 와 Branch
이 그림을 보자 최상단에 root 가 있고 하단에 자신이 가리키는 브랜치 블록들이 있는 것을 볼 수 있다 예를 들어 루트 블록 “서” 레코드가 가리키는 하위 블록은 고객명이 “서” 보다 크거나 같은 또는 작거나 같은 두 개의 블록을 가리키게 됩니다
즉 이런 모양입니다 이 그림만 보면 루트의 왼쪽 브랜치 블록 customName 이 “서” 보다 작거나 같은 인덱스 데이터들이 모여 있는 것이고 오른쪽은 “서” 보다 크거나 같은 인덱스 데이터들이 모여 있는 것입니다
루트 블록은 항상 단 한 개만 존재하며 인덱스의 최상단에 위치하는 것입니다 이때 “서” 가 루트 블록의 기준으로 데이터를 찾을 때 “서” 보다 작은 값은 왼쪽으로 “서” 보다 큰 값은 오른쪽 블록으로 이동하는 형태입니다
브랜치 블록은 이는 루트 블록이 가리키는 하위 블록들을 말합니다 지금 이 그림에는 2개의 브랜치 블록을 가지고 있고 루트 블록을 기준으로 “서” 보다 작거나 같은 값인 데이터는 왼쪽 “강덕승, 김소의, 나지영, 도지원, 박종호” 모두 “서” 보다 작거나 같은 값입니다 (ㄱ ~ ㅎ) 순서를 가지는 것임 그리고 “서” 보다 크거나 같은 값인 데이터는 루트 블록을 기준으로 오른쪽에 위치해 있습니다 “송재훈, 이재홍, 정재우, 최지우, 홍광표” 모두 “서”보다 크거나 같은 값입니다 (ㄱ ~ ㅎ) 순서
LMC
브랜치 블록을 보면 제일 상단에 LMC라는 것이 있다 이는 LeftMostChild로 제일 왼쪽에 있다는 뜻입니다 제일 왼쪽에 있다는 뜻은 해당 블록은 부모의 기준점에서 제일 왼쪽에 있다는 것을 뜻합니다 “서”보다 작거나 같은 브랜치의 LMC는 “강덕승”입니다 이 사람보다 더 왼쪽 데이터 (“강덕승” 보다 순서가 작은 데이터) 가 없기 때문에 “서” 보다 작거나 같은 블록에서 LMC는 강덕승이 됩니다 그리고 “서”보다 크거나 같은 블록의 LMC는 “송재훈”입니다 이 사람보다 더 왼쪽 이때는 “서”보다 크거나 같은 데이터를 만족하면서 “송재훈”보다 순서가 앞에 있는 데이터가 없기 때문에 오른쪽 블록의 LMC는 송재훈입니다
LMC가 중요한 이유
그럼 왜 브랜치 블록들은 이런 LMC를 사용할까? 이는 인덱스의 범위 스캔에 아주 중요한 역할을 하기 때문이다 예를 들어서
1
2
SELECT * FROM custom where customName = '김소의
이런 쿼리가 있다고 하자 루트를 바라보니 LMC 가 “서” 그럼 DBMS는 서를 기준으로 작거나 같은 LMC를 제일 먼저 찾을 것입니다 그리고 그중에서 제일 첫 번째 데이터인 “강덕승”을 확인 결과에 맞지 않으므로 다음 탐색 “김소의” 데이터가 발견되었으므로 멈추게 됩니다 만약 LMC 가 없으면 모든 노드들을 다 찾아봐야 합니다 앞에서 마치 홍길동이라는 학생을 찾을 때 명부 대신 직접 반으로 찾으러 가는 것과 마찬가지인 것입니다
B-Tree 도 변경될 수 있다
지금은 특정 데이터를 기준으로 B-Tree 가 결정되는 것입니다 만약 데이터가 늘어나게 되면 루트 블록이 가득 차게 되면 루트 블록이 브랜치 블록으로 변하고 새로운 루트가 생성됨 새로운 루트가 생기면서 트리의 높이가 증가하게 됩니다
Branch 와 Leaf
Branch 와 Leaf는 Root 와 Branch 와 구조가 같습니다 다음의 사진을 보겠습니다
이번엔 상단 Branch 와 Leaf 블록입니다 마찬가지로 하나의 레코드는 하위 테이블을 가리키는 주솟값을 가지고 있습니다 그렇기에 “강덕승” 이라는 레코드는 “강덕승” 보다 작거나 같은 테이블 블록 1개와 “강덕승” 보다 크거나 같지만 “김소의” 보다 작거나 같은 1개의 데이터 블록 총 2개의 데이터 블록을 가리키게 됩니다 이때 “강덕승”이 양쪽에 있는 것은 한 명의 “강덕승”이 아니라 여려 명의 동일 인물이 있다고 생각하셔야 합니다
이번엔 “강다예” 라는 사람을 찾으려고 한다면 Branch에서 “ㄱ”으로 시작하면서 “ㄴ” 보다 작은 Branch 을 살펴봅니다 먼저 첫 번째 블록은 “강덕승” 을 찾았습니다 여기서 멈추지 않고 다음 레코드를 살펴봅니다 이 이유는 “강덕승” 보다 크면서 “강다예” 보다 작은즉 “강다예” 에 가까운 레코드가 있는지 찾게 됩니다 그리고 다음 레코드인 “김소의”를 보게 되는데 이를 보고 인덱스 스캔은 멈춥니다 “강덕승” < “강다예” < “김소의” 이 순서이기 때문에 DBMS는 “강덕승”이 가리키는 테이블로 찾아가면 “강다예”를 찾을 수 있다고 생각하고 왼쪽 화살표를 따라갑니다 그리고 Leaf 블록에서 하나하나 스캔을 하면서 “강다예”가 나올 때까지 스캔을 하고 결국 “강다예” 찾게 됩니다 이렇게 서술어 식은 복잡할 수 있습니다 그래서 Root부터 전체적으로 정리를 하겠습니다
데이터를 찾아가는 과정
1
2
3
4
5
create index custom_N1 on custom(customName)
Select * From custom where customName = '강다예'
인덱스와 쿼리는 다음과 같습니다
Root의 LMC는 “서”를 가리키고 왼쪽은 “서” 보다 작거나 같은 오른쪽은 “서” 보다 크거나 같은 데이터가 있기 때문에 선택은 “강다예” 데이터는 “서” 보다 작은 데이터이기 떄문에 왼쪽에 있는 브랜치를 선택하게 됩니다
선택받은 왼쪽 Branch는 각각의 레코드를 보면서 자신이 찾고자 하는 데이터를 스캔합니다 이때 자신과 더불어서 다음 레코드를 스캔해서 찾고자 하는 데이터가 범위 안에 들어오는지 확인합니다 “강덕승” < “강다예” < “김소의” 만들어지므로 선택은 “강덕승” 가리키는 Leaf로 찾아가게 됩니다 그리고 해당 블록을 스캔하면서 원하는 데이터를 찾게 됩니다
말로 풀어쓰면 어려워 보이지만 이렇게 순서를 보면 그렇게 어렵지 않다 왜 브랜치 블록이 다음 레코드를 확인해야 하는지도 알게 되었습니다
수직적 탐색 수평적 탐색
인덱스 스캔 시작지점을 찾는것을 수직적 탐색이라고 하고 수직적 탐색을 통해 원하는 데이터를 찾을떄는 수평적으로 찾게 됩니다
이런 구조 입니다