인덱스 기본(1) - 인덱스 구조 및 탐색

 

초등학교에 방문해 홍길동을 찾는 두 가지 방법 

 

1. 1~6학년 모든 교실에서 홍길동 찾기 -> 홍길동이 많을 때 빠름 (테이블 풀)

2. 교무실에서 명부 조회해서 홍길동이 있는 교실만 찾기  -> 홍길동이 별로 없으면 빠름 (인덱스) 

 

이름으로 학생을 찾는 경우가 많다면, 학생명부를 아예 이름순으로 정렬해두면 편하다 이것이 인덱스다.

이름에 딸린 학년-반-번호 컬럼이 인덱스 ROWID에 해당한다. 

 

수십 년에 걸쳐 DBMS가 발전해 왔지만, 조회 방법은 위 두가지 방법에서 크게 벗어나지 못하고 있다.

따라서 SQL 튜닝을 위해 인덱스를 공부하는 것은 매우 중요하다.

 

1. 인덱스 튜닝의 두 가지 핵심요소 

 

인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용한다.  인덱스 튜닝의 핵심요소는 크게 두 가지이다.

 

(1) 스캔 과정에 비효율 줄이기 (인덱스 스캔 효율화 튜닝)

 

ex) 학생명부를 시력순으로 정렬했다면, 똑같은 홍길동을 찾는데 더 오랜 시간이 걸릴 것이다. (홍길동을 찾는 경우)

-> 인덱스가 정렬되어 있다는 점을 꼭 기억하자 

 

(2) 테이블 엑세스 횟수를 줄이기 (랜덤 엑세스 최소화 튜닝) 

 

ex) 시력이 1.0 ~ 1.5인 홍길동 학생을 찾는 경우 시력이 1.0 ~ 1.5인 학생은 50명이고, 이름이 홍길동인 학생은 다섯 명이다. 이 중 시력이 1.0~1.5인 홍길동은 두명 뿐이다. 

시력 순으로 정렬되어 있다면, 더 많은 테이블 엑세스가 발생할 것이다. 

 

*두 요소 모두 중요하지만, SQL 튜닝의 핵심은 랜덤 I/O를 줄이는 것에 있다! 

 

2. 인덱스 구조 

https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=366

인덱스는 책 뒤쪽에 있는 색인과 같은 역할을 한다. 데이터 베이스가 인덱스 없이 검색하면, 처음부터 끝까지 읽어야 한다. 반면, 인덱스를 이용하면 일부만 읽고 멈출 수 있다. 즉 범위 스캔이 가능하다.  이는 인덱스가 정렬되어 있기 때문이다. 

친절한 SQL 튜닝

 

 

루트와 블랜치 블록

• 하위 블록에 대한 주소값을 갖는다.
• 키값은 하위 블록에 저장된 키값의 범위를 나타낸다 ( 예를 들어, 루트 블록 '서'레코드가 가리키는 하위 블록에는 '서'보다 크거나 같은 레코드가 저장돼 있다. (고객명 >= 서)
• 가장 왼쪽 첫 레코드(LMC - Leftmost Child) 키값을 가진 첫 번째 레코드 자식 노드 중 가장 왼쪽 끝에 위치한 블록 LMC가 가리키는 주소로 찾아간 블록에는 키값을 가진 첫 번째 레코드보다 작거나 같은 레코드가 저장돼 있다.                

리프 블록

• 각 레코드가 키값 순으로 정렬돼 있다.
• 테이블 레코드를 가리키는 주소값 (ROWID)를 갖는다. -> 키값이 같으면 ROWID순으로 정렬 

인덱스를 스캔하는 이유는 검색 조건을 만족하는 소량의 데이터를 빨리 찾고 거기서 ROWID를 얻기 위해서다.

ROWID는 DBA와 로우 번호로 구성되므로, 테이블 레코드를 찾아갈 수 있다. 

 

 

3. 수직적 탐색

 

정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정이다. 즉, 인덱스 스캔의 시작지점을 찾기 

수직적 탐색은 루트 블록에서 시작한다. 

루트를 포함한 브랜치 블록에 저장된 각 인덱스는 하위 블록에 대한 주소를 갖는다. 

수직적 탐색 과정에서 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위블록으로 이동한다.

 

ex) 이재희를 찾기 -> 루트에는 이재희보다 크거나 같은 값이 없음 -> 서 레코드가 가리키는 하위블록으로 이동 -> 브랜치 블록에서 이재희보다 큰 정재우를 찾음 -> 바로 직전 레코드(이재룡)이 가리키는 하위 블록으로 이동 -> 리프에 도달하면 조건을 만족하는 첫 레코드를 찾을 수 있다. 

 

수직적 탐색은 조건을 만족하는 레코드를 찾는 과정이 아니라, 조건을 만족하는 첫 번째 레코드를 찾는 과정이다.

 

4. 수평적 탐색

 

수직적 탐색을 통해 스캔 시작점을 찾았으면, 찾고자 하는 데이터가 더 안 나타날 때 까지 리프를 수평적으로 스캔한다.

이 과정이 데이터를 찾는 과정이다. 

리프 블록은 양방향 연결 리스트 구조이므로 좌 우로 탐색이 가능하다. 

 

 

5. 결합 인덱스 구조와 탐색

 

두 개 이상 컬럼을 결합해서 인덱스를 만들 수도 있다. 

친절한 SQL 튜닝

 

> 남자 이재희를 찾는 과정 

> 루트 블록 - 찾고자 하는 값보다 큰 첫 번쨰 레코드를 만남 -> 하위 블록으로 이동 첫 번쨰 남자 이재희 고객을 만날 수 없음 -> 바로 직전 LMC 레코드가 가리키는 하위블록(왼쪽)으로 이동 -> 찾고자 하는 값보다 큰 첫 번쨰 레코드를 만남 -> 성별이 남이면서 정재우 레코드이다. -> 정재우가 가리키는 하위 블록에서 이재희를 찾을 수 없음으로, 바로 직전 남&이재룡이 가리키는 하위블록으로 이동 -> 첫 남&이재희를 리프블록에서 찾았다! -> 남& 이재희보다 큰 값을 만나면 멈춘다.

 

중요한 점은 수직적 탐색을 거쳐서 찾은 인덱스 스캔 시작점이 성별 = '남'이 아니라, 성별이 남이면서 고객명이 이재희인 레코드란 사실을 기억해두자 

 

이때 인덱스의 순서를 바꾸어도, 읽어야하는 인덱스 블록 개수는 똑같다.

인덱스 선두 컬럼을 모두 = 조건으로 검색할 때는 어느 컬럼을 인덱스 앞쪽에 두든 블록 I/O 개수가 같으므로 일량이 같다.

 

---

정리

 

1. 인덱스 튜닝의 핵심 요소 

   - 스캔 과정 비효율 줄이기 -> 인덱스 구성 및 순서에 영향 

   - 랜덤 엑세스 최소화 튜닝 -> 인덱스 구성에 영향 

 

2. 인덱스 탐색 과정 

 

    -> 수직적 탐색을 통해 리프 블록을 찾는다 

          -> 이때 키에는 하위 브랜치의 범위가 담긴다. 

          -> 비교해야하는 값과 키를 탐색하며, 자신의 값보다 같거나 큰 값을 만나면 그 옆의 브랜치로 이동한다.

    -> 수평적 탐색을 통해 값을 찾는다.

          -> 리프 블록의 값을 비교하며 필요한 값을 찾는다.  

          -> 인덱스의 값으로 충분하지 않으면, ROWID를 사용해서 테이블에 접근해서 필요한 데이터를 가져온다

 

3. 결합 인덱스의 탐색은 각각 이루어지는게 아니라, 모든 조건을 만족하는 인덱스를 찾는다

   ex) 성별,이름 순 인덱스에 성별은 남, 이름은 홍길동을 탐색하면, 성별은 남을 찾은 후 그 후에 홍길동을 찾는게 아니라, 

         성별이 남이면서 이름이 홍길동인 데이터를 찾아서 탐색을 시작한다. 

 

---

 

참고자료 

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

친절한 SQL 튜닝 - 예스24