[DB] 인덱스의 수직적 탐색과 수평적 탐색

개발을 하면서 인덱스의 중요성은 알지만 어떻게 동작하는지, 어떤 경우에 유용한지에 대해 깊이 알고있지는 않았다. 창피하지만 면접에서도 제대로 대답하지 못했다.. 이번 기회를 통해 인덱스가 왜 중요한지, 어떻게 인덱스로 테이블 블록에 접근하는지 알아보았다.

인덱스가 중요한 이유

우리는 테이블 블록 접근을 최소화 하기 위한 목적으로 인덱스를 주로 사용하게 되는데, 잘못 사용하게 되면 Table Full Scan 보다 비효율적이다. 

왜냐하면 Table Full Scan은 순차적 I/O를 하고, Index Range Scan은 랜덤 I/O를 하기때문이다.

따라서 인덱스의 효과를 보기 위해서는 인덱스 스캔 과정에서의 비효율을 줄이고, 랜덤 I/O를 최소화해야한다.

인덱스의 구조

인덱스는 기본적으로 B-Tree로 이루어져 있다.(정확히는 B+Tree) B-Tree는 이진 탐색 트리를 조금 더 일반화한 구조로, 루트에서 리프 노드까지의 depth가 동일하다.(한 쪽이 편향되어있지 않다. 그래서 Balanced Tree이다)

• 노드마다 키 값을 기준으로 정렬되어있다.
• 리프 노드에 저장된 레코드는 ROWID(데이터가 저장된 블록 주소 + 로우 번호(OFFSET))를 갖는다.
• 각 노드의 키는 자식 노드의 범위를 나타내는데, 자식 노드의 범위는 키 값보다 크거나 같다.
• 루트와 브랜치 노드에는 LMC(Leftmost Child) 라는 레코드가 저장되어있다. 이 레코드는 자식 노드 중 가장 왼쪽 끝에 위치한 노드를 가리킨다.(키를 가지고 있는 첫번째 레코드보다 작거나 같은 범위)
• 리프 노드끼리는 더블링크드리스트로 앞 뒤로 탐색할 수 있다.

DB Index 구조를 대략적으로 흉내내보았다.

인덱스 탐색

인덱스를 생성하고, 조건절이나 ORDER BY에 인덱스를 조건으로 걸게되면 인덱스를 탐색한다. 인덱스 탐색은 2가지 단계를 거친다.

1. 수직적 탐색(루트 노드부터 리프 노드까지 조건에 일치하는 첫 번째 인덱스를 찾는다.)
2. 수평적 탐색(조건에 일치하는 첫 번째 인덱스부터 마지막 인덱스까지 리프노드를 탐색한다.)

예를 들자면, Employee 테이블에 입사일시가 인덱스로 설정되어있고, 직원 중 2020년에 입사한 직원을 찾고 싶다.2020년도에 가장 빠른 입사일시를 찾는 과정은 아래와 같이 될 것이다.

1. 루트 노드에서 리프 노드까지 탐색하면서 2020년도의 가장 빠른 입사 일시 인덱스를 찾는다.(수직 탐색)
2. 리프 노드를 탐색하며 2022년 중 가장 빠른 입사 일시 인덱스를 만나면 탐색을 멈춘다.(수평 탐색)
3. 그 직전 인덱스까지의 ROWID로 데이터 블록을 탐색한다.

DB Index 구조를 흉내낸 그림이다(내가 직접 그린거라 정확하지 않다)

위의 그림에서 핑크색 화살표가 수직적 탐색이고, 파란색 화살표가 수평적 탐색이라고 볼 수 있다.

조건을 만족하는 첫 번째 인덱스를 찾으면, 리프노드끼리는 더블링크드리스트로 앞뒤로 이동가능하므로 조건에 맞지않는 레코드를 찾을때까지 스캔하면서 ROWID값을 얻는다.

인덱스를 사용할 수 없는 경우

인덱스를 가공하는 경우에는 어떻게 될까?

만약 5월에 입사한 사원들을 알고 싶어 WHERE MONTH(hire_date) = 5 조건을 걸었다고 하자.(hire_date 는 인덱스 컬럼)

이 경우에는 조건에 일치하는 첫 번째 인덱스를 찾을 수 없다.(수직적 탐색을 할 수 없다)

어느 노드로 가야 조건에 맞는 인덱스를 찾을 수 있는지조차 알 수 없기 때문에 모든 리프 노드를 스캔하면서 조건에 일치하는 인덱스들을 찾아야 한다. 이를 Index Full Scan을 한다고 한다.

MONTH(hire_date)가 5인 인덱스를 찾으러면 모든 리프 노드를 스캔해야한다.

사실 예시로 든 경우는 옵티마이저가 Table Full Scan이 더 효율적이라고 판단할 수 있으므로 Table Full Scan이 될 것이다.
Index Full Scan을 유도하고 싶으면 간단하게 인덱스 컬럼만 조회해보면 된다.
SELECT hire_date FROM Employee ORDER BY hire_date

정리

인덱스를 잘 사용하자!

• 인덱스는 수직적 탐색으로 조건에 일치하는 첫 번째 인덱스를 찾고, 수평적 탐색으로 조건에 일치하는 모든 인덱스들을 찾는다.
• 만약 인덱스를 가공하게 된다면 수직적 탐색을 할 수 없기 때문에 모든 리프노드의 인덱스를 탐색해야하므로 비효율적이다.

 

Reference

https://www.yes24.com/Product/Goods/61254539

친절한 SQL 튜닝 - 예스24

https://www.youtube.com/watch?v=bqkcoSm_rCs&t=1884s