주의 : 추가 공부 부분은 저의 개인적인 생각이 꽤나 첨가되어 있어서 정확하지 않을 수 있습니다. 그놈의 수직적 탐색과 수평적 탐색이 궁금해서 찾아보고 정리해봤습니다.
제가 헷갈렸던 부분은 아래 부분입니다. 친절한 SQL 튜닝 책 77쪽 밑에서 5번째줄
수직적 탐색 과정이 '조건에 맞는 레코드를 찾는 과정'이 아닌 '조건을 만족하는 첫 번째 레코드를 찾는 과정'
그런데 찾아보니 이 말 자체가 수직적 탐색은 슈퍼짱짱맨 B*Tree의 힘으로 조건에 맞는 레코드 중 첫번째 레코드를 찾는다는 말이 맞았습니다.
수직적 탐색으로 바로 원하는 레코드를 찾을 수 있습니다. (Index Unique Scan이 그렇게 찾음)
근데 왜 저딴 말을 적어놨을까요?
왜냐면 인덱스 스캔은 Index Range Scan이 일반적이기 때문입니다.
Index Range Scan이 아닌 Index Unique Scan으로 찾는다면, 수직적 탐색으로 조건에 맞는 레코드를 찾을 수 있습니다. 근데 그게 단 1개 뿐이기 때문입니다!
인덱스 레인지 스캔 (Index range Scan)
- (deptno 인덱스가 있다고 가정합니다.)
- 위의 deptno는 유니크하지 않고 많은 사원이 똑같이 20을 가지고 있습니다.
- 그러면 deptno가 20인 것을 만족하는 사원들을 모두 찾아야 합니다.
- deptno = 20 찾기 시작!
- 먼저 수직적 탐색을 해서 쿼리의 where절 조건을 만족하는 첫번째 레코드를 바로 찾습니다.
- 그 후 똑같이 조건을 만족하는 레코드를 수평적 탐색으로 쭈우욱 찾습니다.
- deptno 가 20인 레코드를 수평적 탐색을 통해 다 찾았습니다. 탐색을 종료합니다!
- 위의 과정이 가능한건 인덱스가 순서대로 정렬되어 있기 때문입니다.
인덱스 유니크 스캔 (Index Unique Scan)
Index Unique Scan은 오직 수직적 탐색으로 레코드를 찾을 수 있습니다.
두번째 궁금증
Q, 그러면 수직적 탐색이라면서 정확한 길을 찾으려고 할때, 수평적으로 탐색해 나가는 과정은 뭐냐?
루트 블록이랑 브랜치 블록에는 블록 주소만 있을껀데, 그걸로 어케 정확한 레코드를 찾냐?
정확한건진 모르겠지만, 맥락상으로 저런 수평적 이동도 수직적 탐색의 일부분이라고 생각이 듭니다.
그리고 원하는 조건에 맞는 레코드를 찾는 순간, 같은 조건을 만족하는 레코드를 더 찾아 나서는 과정을 수평적 탐색이라고 합니다.
이때 수평적 탐색은 탐색 방법부터 다릅니다.
각 블록은 수평적으로 앞뒤 리프 블록의 주소를 가지고 있어, 바로 수평적으로 옆 리프블록으로 이동할 수 있습니다.
범위가 넓다면 수평적 탐색으로 여러 인근 리프 블록을 뛰넘으며 탐색할 것 입니다.
수평적 탐색 과정
추가 사진 (B Tree와 B+Tree)
- B Tree
- B+Tree
