[Real MySQL 8.0] 인덱스와 B-Tree 알아보기

🌱 디스크 읽기 방식

💬 HDD (하드 디스크 드라이브) / SSD (솔리드 스레이트 드라이브)

https://texit.tistory.com/15

 

메모리에 비해 실제 하드웨어 장치의 발전은 비교적 느리게 발전한다는 소리를 들은 적이 있을 것이다. 특히 HHD는 플래터(원판)을 돌려서 읽고나 쓰다 보니 성능이 매우 느릴 수밖에 없다. 이를 보완하기 위해 등장한 SSD의 경우 기존 하스크 드라이브에서 데이터 저장용 플래터(원판)을 제거하고 그 대신 플래시 메모리를 장착해서 빠르게 데이터를 읽고 쓸 수 있다. 플래시 메모리는 전원이 없어도 데이터가 삭제되지 않으며, 메모리보다는 느리지만 그래도 하드 디스크 드라이브보다는 훨씬 빠르다.

 

 

💬 랜덤 I/O와 순차 I/O

디스크 읽기 연산에서 '랜덤 I/O'와 '순차 I/O'라는 말을 들은 적이 있을 것이다.

랜덤 I/O나 순차 I/O 모두 하드 디스크 드라이브 플래퍼(원판)을 돌려서, 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 다음 데이터를 읽는 것이다. 하지만, 순차 I/O의 경우 3개의 페이지를 기록할 때 1번의 시스템 콜을 사용하지만, 랜덤 I/O는 3번의 시스템 콜을 요청한다. 이는, 랜덤 I/O의 경우 읽어야 하는 데이터가 물리적으로 불연속한 위치에 존재하기 때문에 헤드를 이동시키고 시스템 콜을 호출하지만, 순차 I/O는 그대로 읽기만 하면 되기 때문에 1번이면 충분하기 때문이다. 즉, 순차 I/O가 랜덤 I/O보다 약 3배 빠르다는 것이다. 그래서 여러 번 쓰기나 읽기를 하는 랜덤 I/O 작업이 부하가 더 크다.

💡 SSD의 경우 플래터가 없어서 별 차이가 없다고 생각할 수 있다. 
하지만, SSD에서도 순차 I/O에 비해 랜덤 I/O의 throughout은 떨어진다고 한다.

기본적으로 디스크의 성능은 얼마나 많은 데이터를 한 번에 기록하느냐에 의해서 결정된다.
랜덤 I/O와 순차 I/O 모두 파일 쓰기 실행 시 동기화 작업 (flush or fsync) 작업이 필요한데, 순차 I/O의 경우 동기화 작업이 너무 빈번하면 랜덤 I/O처럼 비효율적으로 처리할 수 있어서 보통 RAID 컨트롤러의 캐시 메모리의 경우 효율적으로 순차 I/O를 처리할 수 있도록 도와주기도 한다.

 

보통 쿼리를 튜닝한다는 것은 랜덤 I/O를 어떻게 줄이는 것인지가 포인트이다.

밑에서 다루겠지만, 인덱스 레인지 스캔은 데이터를 읽을 때 랜덤 I/O를 사용하고 풀 테이블 스캔은 순차 I/O를 사용하는데, 오히려 테이블에 데이터가 굉장히 많고 해당 데이터의 대부분을 조회하는 경우에는 일부러 풀 테이블 스캔을 사용하여 역으로 순차 I/O를 통해 처리하는 경우도 존재한다. 순차 I/O의 경우 더 빠르고 많은 데이터를 읽을 수 있어서 OLTP (On-Line Transaction Processing) 성격의 서비스보다 통계 작업에서 자주 사용된고 한다.

 

- 클러스터링 인덱스를 활용해서 레인지 스캔을 하게 되면, 실제 물리적인 쿼리 위치가 정렬된 상태를 유지하기 때문에 "데이터를 순서대로 조회한다면" 랜덤 I/O가 아닌 순차 I/O를 진행하게 된다. 물론, 순서대로가 아닌 중간중간 몇 개씩만 데이터를 조회한다면 랜덤 I/O를 진행하게 될 것이다.

- 반대로, 세컨더리 인덱스를 사용하게 되면 클러스터링 인덱스를 가리키고 있고, 물리적인 위치가 정렬되지 않기 때문에 분산이 되어 있을 것이다. 그래서 순차 I/O에 비해서 랜덤 I/O를 사용하여 동작하게 될 것이다. 

 

---

🌱 인덱스

인덱스란 컬럼의 값과 해당 레코드가 저장된 주소를 key-value로 삼아 만드는 것을 의미한다. 이때, 컬럼의 값은 주어진 순서대로 미리 정렬해서 보관하며, 인덱스가 많은 테이블은 CUD 작업은 느리지만, R에서 독보적인 성능을 보인다.

 

 

🌱 프라이머리 인덱스와 세컨더리 인덱스

프라이머리 인덱스는 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스로, 테이블에서 레코드를 식별할 수 있는 기준값을 사용한다. 기본적으로 NULL과 중복을 허용하지 않는다. 반대로 세컨더리 인덱스는 PK를 제외한 나머지 필드로 인덱스를 만들었을 때 생성되는 것을 의미한다. 유니크 인덱스의 경우 대체 키라고도 하는데, 세컨더리 인덱스로 볼 때도 있고 그냥 아예 별도로 분리할 때도 있어서 알아만 두자.

 

 

🌱 B-Tree 인덱스 (Balanced Tree)

인덱스 구조 중에 가장 많이 사용하는 타입은 B-Tree이다. (AVL 등 다른 구조도 있지만, B-Tree가 블록 단위로 데이터에 대한 I/O 작업을 진행할 때 가장 효율적으로 사용할 수 있기 때문이다.) 인덱스는 페이지 단위로 저장되며, 인덱스 키를 기준으로 항상 정렬된 상태를 유지한다는 것이 특징이다.

왼쪽에 있는 부분이 B-Tree 인덱스라고 생각하면 되고 (루트 노드 생략), 오른쪽이 프라이머리 키 인덱스이다. (= 클러스터 인덱스) 

최상위는 루트 노드, 중간은 브랜치 노드, 가장 하위는 리프 노드라고 말하는데, 루트와 브랜치는 본인의 하위 자식 노드의 주소를 가지고 있으며, 리프 노드의 경우 데이터 파일에 저장된 레코드 주소를 가지고 있다. 또한, 인덱스의 키 값은 항상 정렬되어 있지만 데이터 파일의 레코드는 정렬이 되어 있지 않아서 일반적인 DBMS에서는 INSERT 순서로 저장하는 것이 아닌 중간에 DELETE로 인해 비어있는 공간이 생기면 해당 위치에 삽입이 진행된다. (즉, 임의의 순서) 하지만, 특별하게 innoDB의 경우 레코드가 클러스터되기 때문에 PK 순서대로 정렬되어 저장되기 때문에 PK 자체가 ROWID (실제 레코드의 물리적인 주소) 역할을 하며, 이로 인해 PK가 '논리적인 주소'를 가진다고 말한다. (myISAM에서는 세컨더리 인덱스가 물리적인 주소를 가짐)

 

그래서 innoDB 테이블은 인덱스를 통해 데이터를 읽어도 바로 데이터 파일을 찾을 수 없으며, 인덱스 영역에 저장된 PK를 통해 PK 인덱스를 한 번 더 검색한 다음, PK 인덱스의 리프 페이지에 저장된 레코드를 읽는다. 즉, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽으려면 PK를 저장하고 있는 B-Tree를 다시 검색해야 한다.

 

참고로, 기본적으로 PK로 레코드를 조회할 때 데이터 파일은 정렬되어 있지 않아서 PK 자체가 어느 페이지에 저장되어 있는지 알 수 없기 때문에 랜덤 I/O 발생 후, 해당 PK 값을 따라가서 리프 노드에 저장된 실제 레코드를 받아오게 되는 것이다.

 

---

 

🌱 B-Tree 인덱스 키 추가

B-tree에 새로운 키를 추가하기 위해서는 저장될 위치를 결정한 다음, 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 인덱스에 저장한다. 만약, 리프 노드가 꽉차면 해당 노드를 분리하는데, 이때 상위 브랜치 노드까지 처리 범위가 넓어져서 새로운 키를 추가하기 때문에 (부모로 승격하는 것) 해당 연산은 비용이 많이 드는 작업이다.

보통 레코드 추가 작업이 1이라면 테이블의 인덱스에 키를 추가하는 비용은 1.5 정도로 측정하며, 예를 들어 인덱스가 3개라면 1.5 * 3 + 1 = 5.5 정도를 비용으로 생각한다. innoDB에서는 체인지 버퍼를 활용하여 인덱스 키를 추가하는 작업을 지연시킬 수 있지만, PK, UK 같이 유니크 제약 조건이 걸려있을 경우 중복 체크를 해야 하기 때문에 즉시 B-Tree에 추가하거나 삭제하는 작업을 진행한다.

 

💡 체인지 버퍼
체인지 버퍼는 특정 데이터 페이지가 버퍼 풀에 없을 때 세컨더리 인덱스 페이지에 대한 변경 사항을 캐시하는 데이터 구조이다,
인덱스 삽입 / 업데이트 시 디스크에 대한 랜덤 I/O 연산이 비용이 크기 때문에 변경이 필요한 인덱스 페이지가 버퍼 풀에 있으면 바로 업데이트를 하고, 디스크로부터 읽어와야 한다면 인서트 버퍼에 저장했다가 사용자에게 결과를 바로 반환하도록 최적화한다.
- 지연된 작업은 추후 다른 읽기 작업을 통해 버퍼 풀에서 페이지 로드 시 merge

- 사용자 쿼리 실행 -> 버퍼 풀에 변경 사항이 발생한 페이지 (B-Tree의 리프 노드) 있다면 즉시 변경 사항 반영 -> 버퍼 풀에 페이지 없으면 인서트 버퍼에 임시로 기록해두고 쿼리 실행 완료 -> 추후 인덱스 페이지를 읽을 때마다 인서트 버퍼에서 머지해야 하는 키값을 확인한 다음 병합 (B-Tree 인덱스 반영)

 

---

🌱 B-Tree 인덱스 키 삭제

인덱스 키 삭제 시 삭제할 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마킹 처리를 진행한다. 마킹된 공간은 방치할 수도 있고, 재활용할 수도 있는데 마킹 작업 역시 디스크 I/O 작업이 필요해서 비용이 크다. 마찬가지로 MySQL 5.5 이상부터는 인덱스 추가처럼 지연 처리가 가능하다.

 

---

🌱 B-Tree 인덱스 키 변경

인덱스 키 값은 해당 값에 따라 저장될 리프 노드의 위치가 결정되기 때문에, B-Tree의 키 값이 변경되면 인덱스의 키 값만 변경하는 것은 불가능하다. 그래서 보통 먼저 키 값을 삭제한 뒤 새로운 키 값을 추가한다. 변경 역시 마찬가지로 지연 처리가 가능하다.

 

---

🌱 B-Tree 인덱스 키 검색

기본적으로 키 탐색 시 ‘트리 탐색’ 기법을 사용하여 조회한다.

100% 값이 일치하는지 찾는 equality 비교나 부등호 비교 조건, 혹은 like에서 앞부분만 일치하는 경우 (like%)에 대해서 인덱스가 걸린 필드를 사용하면 가능하지만, 인덱스 값을 변형한 다음에 사용한다면 빠른 검색을 활용할 수 없다.

또한, innoDB 테이블의 경우 검색 시 넥스트 키 락이나 레코드 락을 통해서 인덱스를 잠그고 테이블의 레코드를 잠그기 때문에, UPDATE / DELETE 시 테이블에 사용할만한 인덱스가 없으면 불필요하게 많은 레코드를 잠글 수 있기 때문에 인덱스 설계를 잘해야 한다. (테이블 전체에 락이 걸릴 수도 있으니 주의해야 함)

 

---

🌱 B-Tree 인덱스 사용 시 고려할 요소

B-Tree에서 인덱스를 사용할 때 인덱스를 구성하는 컬럼의 크기와 레코드 건수, 유니크한 인덱스 키 값의 개수 등을 잘 설정해야 한다.

 

💬 인덱스 키 값의 크기

innoDB의 데이터 저장 시 가장 기본 단위를 페이지 or 블록이라고 한다. (버퍼 풀에서 데이터를 버퍼링하기 위한 기본 단위이기도 하다) 이때, 인덱스 역시 페이지 단위로 관리되며, 루트, 브랜치, 리프 노드를 구분하는 기준이 ‘페이지’이다. (기본은 16KB)

일반적으로 B-Tree 구조에서 자식 노드의 개수는 가변적이기 때문에 인덱스의 페이지 크기와 키 값의 크기에 따라서 결정된다.

위 그림을 기준으로 하면 하나의 인덱스 페이지에 총 16*1024/(16+12) = 585개의 키를 저장할 수 있으며, 자식 노드를 585개 가질 수 있는 B-Tree가 된다. (현재 키 값은 16바이트) 하지만, 인덱스 키 값이 32바이트로 늘어난다면 16*1024/(32+12) = 372개가 저장되며, 만약 한 번 SELECT 시 500개 이상의 데이터를 읽어야 한다면 두 번째 경우는 디스크를 2번 읽어야 해서 더 느려지게 된다.

💡 즉, 인덱스 키 값이 길어지면 전체적인 인덱스의 크기도 커지기 때문에, 제한된 크기의 버퍼 풀에서 하나의 레코드를 위한 인덱스 크기가 커지면 메모리에 캐시할 수 있는 레코드의 수가 줄어들어 결국 효율성 역시 떨어지게 된다.

 

💬 B-Tree 깊이

B-Tree의 깊이는 직접 제어가 불가능하다. 만약 B-Tree의 깊이가 3이라고 가정한다면 위의 예제에서 최대 2억 (585^3)을 가지지만, 인덱스 키 값이 32바이트라면 최대 5천만 (372^3)이라서 줄어들고, 결국 디스크 접근 횟수가 또 늘어나는 결과를 초래한다. 웬만하면 깊이는 작게 만들자.

 

💬 선택도(Selectivity) = 기수성(Cardinality)

선택도란 모든 인덱스 키 값중 유니크한 값의 수를 의미한다. 만약 테이블의 레코드에서 중복값이 많아졌다면 기수성이 낮다고 볼 수 있고, 기수성이 낮으면 검색해야 하는 대상이 많아져서 속도가 느려지게 된다.

ex) 전체 레코드 수는 10000개일 때 쿼리 조건에 일치하는 레코드가 1개라면?
이때, 특정 컬럼 A에 대해 유니크한 값의 개수가 10개라면 9개를 더 읽게 되는 것이고, 유니크한 값의 개수가 1000개라면 999개를 더 읽은 것이 된다. 즉, 후자의 경우가 비효율적인 방식이 된다.

하지만, A 컬럼에 인덱스를 걸었다면 인덱스된 컬럼에 대해서 전체 레코드의 개수나 유니크한 값의 개수 등의 통계 정보를 가지고 있다. (인덱스별로 평균 몇 개의 레코드가 있는지 미리 계산하는 것) 이때 전자의 경우 10000 / 10 = 1000개를 미리 읽게 되어, 1개만 일치한다면 999개가 낭비된다. 반면, 후자의 경우 10000 / 1000 = 10개를 미리 읽게 되어, 9개가 낭비되기 때문에, 인덱스를 걸면 오히려 결과가 반대되는 것을 볼 수 있다. 그래서 인덱스의 경우 유니크한 값의 개수가 많을수록 더 효율적이다.

 

---

 

🌱 데이터를 몇 개나 읽어와야 할까?

일반적인 DBMS의 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 게 직접 레코드에서 데이터를 읽는 것보다 4~5배 정도 비용이 많이 든다고 예측한다. 그래서 인덱스를 통해 읽을 레코드의 개수가 전체 테이블 레코드의 20~25%를 넘는다면 인덱스를 사용하지 않고 그냥 풀테이블 스캔 + 필터링이 더 효율적이다.

 

---

💬 인덱스 레인지 스캔

검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방법이다. 루트 노드부터 비교를 시작해서 브랜치 노드를 거치고, 최종적으로 리프 노드까지 찾아 들어가야 필요한 레코드의 시작 지점을 찾을 수 있다. 시작 지점을 찾은 이후, 리프 노드의 데이터만 순서대로 읽으며, 하나의 리프 노드를 다 읽으면 다음 리프 노드로 이동해서 또 다시 스캔한다. 이때, 인덱스의 특성으로 인해 오름차순 / 내림차순으로 정렬된 상태로 데이터를 가져오게 된다. 그리고, 조건을 다 찾으면 반환 후 쿼리를 종료한다.

SELECT * FROM crew WHERE name BETWEEN Ice AND Journey

리프 노드 5번 페이지에 도달하기 위해서 루트 노드, 브랜치 노드에서 찾아들어간다. 이후 찾은 다음에는 쭉 레인지 스캔을 진행하며 ‘Journey’ 레코드를 찾을 때까지 쭉 스캔하다가 찾으면 반환하게 된다. 

 

단, 인덱스의 리프 노드에서 검색 조건에 일치하는 것들의 레코드 주소 값을 바탕으로, 데이터 파일로부터 읽어와야 하기 때문에 (일치하는 개수만큼 디스크에서 처리해야 함) 랜덤 I/O 작업이 발생하여 비용이 상당히 크다. 

 

💡 인덱스 레인지 스캔 과정
1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. (index seek) 
2. 탐색된 위치로부터 필요한 만큼 인덱스를 읽어나간다. (index scan)
3. 읽은 인덱스 키와 레코드 주소를 통해 데이터 페이지를 가져오고, 저장된 레코드를 읽어온다. (랜덤 I/O)
- 만약 커버링 인덱스를 사용한다면 디스크의 레코드를 읽어오지 않기 때문에 랜덤 읽기가 줄어들고 성능이 빨라진다.

커버링 인덱스란 쿼리를 충족시키기 위한 모든 데이터를 가지고 있는 인덱스로, where, order by, group by 등 조건절에 대해서 사용되는 모든 컬럼이 인덱스 컬럼에 포함되는 경우를 의미한다.

- index seek, index scan 과정은 mySQL에서 다음과 같은 쿼리로 알 수 있다.

SHOW STATUS LIKE 'handler_%';

- handler_read_key: index seek가 실행된 횟수

 

- handler_read_next, handler_read_prev: index scan에서 읽은 레코드 개수
handler_read_next: 인덱스 정순으로 읽은 레코드 개수 / handler_read_prev: 인덱스 역순으로 읽은 레코드 개수

 

- handler_read_first, handler_read_last: 인덱스의 첫 번째, 마지막 레코드를 읽은 횟수
보통 MIN(), MAX() 같이 값이 가장 작거나 큰 값을 읽을 때만 증가한다.

 

참고 - 여기서 모두 인덱스만 읽었는지, 인덱스로 테이블의 레코드만 읽었는지는 구분하지 않는다.

 

---

 

💬 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식으로, 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아니라면 보통 인덱스 풀 스캔이 발생한다.
ex) 인덱스가 A, B, C 순서지만 쿼리에서는 B, C 컬럼으로 검색하는 경우
인덱스 리프 노드의 제일 앞, 뒤로 이동한 다음, 처음부터 끝까지 스캔한다. 

물론, 인덱스가 테이블 크기보다 작기 때문에 테이블 풀 스캔에 비해서는 좀 더 효율적이다.
- 당연히 쿼리에서 필요한 컬럼들이 인덱스에 존재해야 테이블 스캔이 안 일어난다. (다른 컬럼까지 필요하다면 테이블 스캔 발생)

 

---

💬 루스 인덱스 스캔

레인지 스캔이랑 비슷하지만, 중간에 필요하지 않은 인덱스 키는 무시하고 다음으로 넘어가는 방식이다. GROUP BY, MIN(), MAX()에 대해 최적화를 하는 경우 사용한다.

SELECT name, MIN(age)
FROM crew
WHERE id BETWEEN 1 AND 100
GROUP BY id;

 

crew 테이블은 (id, age)로 인덱스가 생성되어 있고, 정렬까지 되어 있는 상태라고 가정해보자.
그렇다면 위의 쿼리를 처리할 때 id 그룹별로 첫 번째 레코드의 age 값만 읽으면 되기 때문에 조건에 만족하지 않는 레코드는 무시하고 스캔을 진행한다.

 

---

💬 인덱스 스킵 스캔

ALTER TABLE crew ADD INDEX idx_gender_birth (gender, birth);

 

crew 테이블에 위와 같이 성별과 생일 정보를 가진 복합 인덱스를 만들어보자.
이때, 위의 인덱스를 사용하기 위해서는 gender에 대한 조건이 꼭 들어가야 했었다.

하지만, MySQL 8.0부터는 birth 컬럼으로도 인덱스 검색이 가능하게 해주는 ‘인덱스 스킵 스캔’ 최적화 기능이 도입되었다!
- explain으로 실행 계획을 보면 type에 range라고 떠있을 것이다.

- gender 컬럼에서 유니크한 값을 다 조회한 다음, 쿼리에 gender 컬럼을 내부적으로 알아서 추가해서 다시 실행하는 형태로 처리된다.

 

SELECT gender, birth FROM crew WHERE birth >= '2001-03-12'

# 내부적으로 아래와 같이 쿼리 생성 후 최적화
SELECT gender, birth FROM crew WHERE birth >= '2001-03-12' AND gender = 'W'
SELECT gender, birth FROM crew WHERE birth >= '2001-03-12' AND gender = 'M'

 

enum 값이 아니더라도 인덱스에 존재하는 모든 값을 먼저 추출하고, 이를 바탕으로 인덱스 스킵 스캔을 진행한다.
하지만, 위 기능을 사용하려면 ‘조건이 없는 인덱스의 컬럼의 유니크한 값의 개수가 적어야 하고’, ‘쿼리가 인덱스에 존재하는 컬럼만으로 처리가 가능해야 한다. (커버링 인덱스)’ 만약, 유니크한 값이 많아지면 스캔 시작 지점을 검색하는 작업도 많이 필요해질 것이다. 예를 들어 (gender, birth)라면 gender의 개수만큼 스캔 시작 지점이 생기게 되는 것이니까 유니크한 값이 적어야 한다는 것.

만약, 인덱스 외에 다른 컬럼이 필요하다면 풀 테이블 스캔을 통해서 실행 계획을 수립한다.

 

---

💬 다중 컬럼 인덱스 (복합 인덱스)

여러 개의 컬럼을 포함하는 인덱스이다. 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬되어 있기 때문에, 첫 번째 컬럼이 똑같은 레코드에 대해서만 유의미하므로, 각 컬럼의 순서는 상당히 중요한 포인트이다.

 

---

🌱 B-Tree 인덱스의 정렬과 스캔 방향

기본적으로 인덱스의 키 값은 항상 오름차순 / 내림차순으로 정렬된다.

 

💬 인덱스의 정렬

mySQL 8.0부터는 정렬 순서를 혼합한 인덱스를 사용할 수 있다.

CREATE INDEX idx_name_age ON crew (name ASC, age DESC);

💬 인덱스 스캔 방향

인덱스는 항상 오름차순으로 정렬되어 있지만, 최솟값부터 읽으면 오름차순으로 가져오고 최댓값부터 읽으면 내림차순으로 값을 가져올 수 있다. 즉, 쿼리가 인덱스를 사용하는 시점에 효율적인 방법을 선택하는 것이다.

SELECT * FROM crew 
WHERE name >= 'journey' 
ORDER BY name ASC
LIMIT 4;

이 쿼리의 경우 name의 인덱스를 통해 ‘journey’ 레코드를 찾은 다음, 정방향으로 인덱스를 읽으면서 4개를 가져오면 된다. (ASC)

SELECT * FROM crew 
ORDER BY name DESC
LIMIT 4;

 

반면에 이 쿼리의 경우 name 인덱스를 역순으로 읽어서 4개만 가져오면 된다. (DESC)

 

💬 내림차순 인덱스

복합 인덱스에서 내림차순, 오름차순이 혼합되어 있다면 ‘내림차순 인덱스’의 사용도 고려해야 한다.
소량의 레코드를 대상으로 한다면 그냥 그대로 사용해도 되지만, 대량의 레코드를 대상으로 한다면 내림차순 인덱스가 더 효율적일 수 있다.

위 그림에서 4가지의 키워드를 얻어낼 수 있다.

- 오름차순 인덱스: 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
- 내림차순 인덱스: 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
- 인덱스 정방향 스캔: 인덱스 리프 노드의 왼쪽 → 오른쪽으로 스캔 (순서대로 읽는 것)
- 인덱스 역방향 스캔: 인덱스 리프 노드의 오른쪽 → 왼쪽으로 스캔 (반대 방향으로 읽는 것)

보통 인덱스 정방향 스캔이 좀 더 빠르게 이루어진다. 이는 페이지 잠금이 인덱스 정방향 스캔에 좀 더 적합하게 설계되었으며, 페이지 내의 인덱스 레코드가 단방향으로만 연결되어 있기 때문이다.

- 리프 노트의 페이지는 이중 연결 리스트로 되어 있는데, 페이지 락 과정에서 데드락 방지를 위해 락을 획득하는 게 정방향에서만 가능하고, 역방향에서는 좀 복잡하기 때문이다. 그래서 구조적으로 인덱스 스캔에는 정방향이 좀 더 적합한 느낌?

- 또한, 인덱스는 페이지 내부에서 4~8개 정도 묶어서 그룹을 만들어, 해당 그룹의 대표키를 뽑아 리스트로 관리한다. (= 페이지 디렉터리) 근데 이 디렉터리가 단방향으로 연결되어 있다 보니 역방향으로 접근이 안 되어서 더 느린 것.
ex) 오름차순 인덱스라면 키값이 오름차순으로 정렬되어 있어 정방향 스캔이 빠른데, 내림차순 인덱스라면 키값이 내림차순으로 정렬되어 있어 역방향 스캔이 좀 더 빠른 느낌... 인 것 같다.

그래서 역방향 스캔을 사용한다면 내림차순 인덱스를 고려해보자.

SELECT * FROM crew
WHERE id = ?
ORDER BY name DESC
LIMIT 10;

 

위의 쿼리에 대해서 소량이라면 오름차순, 대량이면 내림차순을 사용하는 게 좋다.
오름차순 인덱스: INDEX (id ASC, name ASC);
내림차순 인덱스: INDEX (id DESC, name DESC);

 

---

 

🌱 B-Tree 인덱스의 가용성과 효율성

💬 비교 조건의 종류와 효율성

SELECT * FROM crew
WHERE course = 'Backend' and age >= 23;

 

위와 같은 쿼리에 아래와 같은 인덱스가 추가되었다고 생각해보자.

INDEX (course, age)
INDEX (age, course)

 

첫 번째 인덱스의 경우 course = 'Backend' and age >= 23인 레코드를 찾은 다음, course=’Backend’가 아닐 때까지 인덱스를 그냥 쭉 읽는다. 이때는 읽은 레코드가 모두 조건절에 해당하는 레코드가 된다.

 

하지만 두 번째 인덱스의 경우 age >= 23 and course = 'Backend'인 레코드를 찾고, 모든 레코드에 대해서 course=’Backend’인지 경우를 찾아야 한다. (필터링) 왜냐면 course의 경우 age를 기준으로 정렬이 되기 때문에 ‘course’라는 컬럼은 비교 작업을 좁히는데 도움을 주지 않기 때문이다. 단순히 해당 값이 일치하는지에만 사용된다.

여기서 첫 번째 인덱스의 course = 'Backend' and age >= 23을 작업 범위 결정 조건, 두 번째 인덱스의 course = 'Backend'를 체크 조건이라고 한다.

 

---

💬 인덱스의 가용성

B-Tree 인덱스는 왼쪽 값을 기준으로 오른쪽 값이 정렬되어 있다. 그래서 왼쪽 부분이 없으면 인덱스 레인지 스캔이 안 된다.
단일 인덱스의 like 검색에서 위 상황을 볼 수 있다.

SELECT * FROM crew WHERE name like '%nez';

 

name 컬럼에 저장된 값을 한 글자씩 비교해가며 일치하는 레코드를 찾아야 하지만, 위와 같이 왼쪽 부분이 고정되지 않았다면 인덱스의 효과를 보기 어렵다.

또한, 복합 인덱스 인덱스의 경우 선행 컬럼이 없다면 문제가 발생한다.

SELECT * FROM crew WHERE age >= 20;

 

여기서 course 정보에 대한 조건절이 아닌, age에 대한 조건절이라면 효율적으로 인덱스를 사용할 수 없다.

 

---

💬 가용성과 효율성 판단

다음과 같은 조건에서 B-Tree 인덱스를 사용할 수 없다. (작업 범위 결정 조건으로 사용이 불가능)

- NOT EQUAL 비교

WHERE name <> ‘journey’
WHERE name NOT IN (’journey’, ‘hello’)
WHERE age NOT BETWEEN 20 AND 23
WHERE name IS NOT NULL

 

- LIKE ‘%??’

WHERE name LIKE ‘%ney’
WHERE name LIKE ‘_ney’
WHERE name LIKE ‘%our%’

- 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우

WHERE SUBSTRING (name, 1, 1) = ‘J’
WHERE DAYOFMONTH(date) = 1

- NON-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 있을 경우

WHERE name = function()

- 데이터 타입이 서로 다른 비교

WHERE char_column = 20

- 문자열 데이터 타입의 콜레이션이 다른 경우

WHERE utf8_bin_char_column = euckr_bin_char_column

참고로, MySQL에서는 NULL도 인덱스에 저장된다.

다중 컬럼 인덱스는 아래와 같은 경우에 적용이 안 된다.

CREATE INDEX idx_example (col_1, col_2, col_3, ... col_n)

 

- col_1에 대한 비교 조건이 없는 경우
- col_1에 대한 비교 조건이 위에서 봤던 사용할 수 없는 경우에 속하는 경우

 

적용 가능한 경우는 다음과 같다. (i는 2 이상 n 미만)
- col_1 ~ col_(i-1)까지 동등 비교 형태일 때 (=이나 in)
- col_i에 대해 동등 비교 (=이나 in), 크고 작음 비교 (<, >), like로 좌측 일치 비교 (like ‘jour%’)
이때 col_1 ~ col_i는 작업 범위 결정 조건으로, col_i+1 ~ col_n은 체크 조건으로 사용된다.