B-Tree 인덱스

Balanced-Tree.

리프 노드, 브랜치 노드, 리프 노드로 구성.

인덱스 구조체 내에서 항상 정렬된 상태로 유지됨.

B-Tree 인덱스의 리프 노드는 항상 실제 데이터 레코드를 가르키는 주소값을 가지고 있다.

페이지 -> 페이지를 연결하고, 리프 노드에 데이터 레코드. 리프 노드가 아니면, 인덱스는 기본적으로 테이블의 key column만 가지고 있음.

트리 구조 때문에, 중간에 UPDATE가 있으면 INSERT 순서와 다르게 정렬 될 수 있음.

인덱스 키 삽입, 삭제, 수정, 검색

삽입은 적절한 위치의 리프 노드에 저장, 리프가 꽉 차면, 리프를 분리. 작업 비용이 많이 든다.

삭제는 리프 노드를 찾아 삭제 마스킹만 하면 된다. 지연 처리가 가능하다.

수정은 삭제, 삽입 두 단계로 나눠서 진행된다.

검색은 비교 연산, 키 값의 앞 부분 일치 조건 등으로 빠르게 트리 탐색이 가능하다. 인덱스 키 값에 변형이 가해진 후 비교되는 경우에는 빠른 검색이 불가능하다.

트리의 크기

자식 노드의 개수는, 페이지 사이즈 시스템 변수에 영향을 받음.

인덱스의 키가 16바이트이고, 자식노드 주소 영역이 12바이트라고 가정해보자. 하나의 인덱스 페이지가 16KB라면, 16*1024/(16+12) = 585 개를 저장할 수 있다. 이를 최대 깊이 3인 경우로 생각해보면 585 * 585 * 585인, 2억개 정도를 저장 가능하다.

하지만 인덱스 키가 2배로 늘어나면, 372 * 372 * 372 인, 5천만개 정도로 줄어든다.

트리의 깊이가 깊어질 수록 디스크를 읽어야 하는 횟수도 늘어나고, 저장 가능한 레코드 수가 줄어들어, 메모리 효율이 떨어지게 된다.

트리의 깊이는 아무리 대용량 서비스라도, 5단계 이상까지 깊어지는 경우는 흔치 않다.

| 인덱스를 통해 레코드를 읽는 작업은, 직접 레코드를 읽는 것보다 4~~5배 비싼 작업이다. 따라서 읽어야 할 레코드가 전체 테이블 레코드의 20~~25%를 넘어가는 경우에는, 인덱스를 활용하지 않고, 전체 테이블을 읽는(필터링) 방식이 효율적이다.

데이터 읽기

index range scan
- 범위로 인덱스를 가져오는 경우 SELECT * FROM a WHERE first_name BETEWEEN '가' AND '나';
1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다.
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽는다.
3. 2번에서 읽은 인덱스 키로 레코드를 가져온다.
- 순서가 유지된다.
index full scan
- 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우
- 테이블 풀 스캔보다 효율적임. 인덱스 전체의 크기가 테이블 자체 크기보다 작기 때문. -> 적은 디스크 I/O로 쿼리 처리 가능.
loose index scan
- 느슨하게 듬성듬성 인덱스를 읽는 방법
- group by, max, min 등의 최적화에 활용

가용성과 효율성

그렇다면 어떤 경우에 index를 사용할 수 있고, 언제 index를 생성해야 할까요?

다중 컬럼 인덱스에서 인덱스의 순서가 중요한 경우가 존재합니다.

SELECT * FROM users
  WHERE user_no='a001' AND emp_no >= 10123;

이 쿼리에는 INDEX(user_no, emp_no), INDEX(emp_no, user_no) 중에 어떤 순서가 더 효율적일까요?

결론부터 확인하면, 이 쿼리에서는 INDEX(user_no, emp_no) 순서가 더 효율적입니다.

이 쿼리에는 두 가지 조건이 있습니다.

user_no = 'a001' : 동등 비교 (Equality)
emp_no >= 10123 : 범위 조건 (Range)

mysql에서 다중 컬럼 인덱스는 왼쪽부터 차례대로만 사용이 가능합니다.

INDEX(user_no, emp_no)

user_no = 'a001' 이므로 첫 번째 컬럼인 user_no 조건 충족 이후 emp_no >= 10123도 인덱스를 통해 범위 탐색 가능합니다. 이는 Index Range Scan이 잘 작동하여 효율적입니다.

INDEX(emp_no, user_no)

여기서는 emp_no >= 10123부터 평가하려 하지만, emp_no는 범위 조건이기 때문에, 그 다음 컬럼인 user_no는 인덱스에서 사용할 수 없습니다. 즉, 이 인덱스를 사용하면 user_no = 'a001' 조건은 인덱스 레벨에서 처리되지 못하고, 필터링 단계에서 처리됩니다.