B-Tree index

구조 및 특성

출처: https://wonsjung.tistory.com/598

그림과 같이 인덱스의 키값은 모두 정렬되어 있지만, 실제 데이터가 저장된 데이터 파일에는 임의의 순서로 저장되어 있다. 레코드가 삭제되어 빈 공간이 생기면 그다음 INSERT는 삭제된 공간을 재활용하도록 DBMS가 설계되어 있기 때문에 항상 INSERT 순서로 저장되지 않는다.

대부분의 RDMS는 임의의 순서로 저장된다.

하지만 InnoDB 테이블에서 레코드는 클러스터 되어 디스크에 저장되므로 기본적으로 PK 순서로 정렬되어 저장된다. 다른 DBMS에서는 클러스터링 기능이 선택 사항이지만, InnoDB에서는 디폴트로 클러스터링 테이블이 생성된다.

클러스터링이란 비슷한 값을 모아서 저장하는 방식을 의미한다.

인덱스는 테이블의 PK 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 실제 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 실제 데이터가 존재하는 데이터 파일에서 레코드의 주소를 갖는다.

[MyISAM의 index table]

출처: https://wonsjung.tistory.com/598

MyISAM 엔진의 경우, 테이블 생성 옵션에 따라 레코드가 테이블에 INSERT 된 순서이거나 데이터 파일 내의 위치(Offset)이다.

MyISAM과 InnoDB 스토리지 엔진의 인덱스에서 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법에 있다. MyISAM은 세컨더리 인덱스가 물리적인 주소를 가지는 반면, InnoDB는 PK를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다.

[InnoDB의 index table]

출처: https://wonsjung.tistory.com/598

그래서 InnoDB에서 인덱스를 통해 레코드를 조회할 때, 데이터 파일을 바로 찾아가지 못한다.

그림과 같이 인덱스에 저장돼 있는 PK 값을 이용해 PK 인덱스를 한 번 더 검색한 후, PK 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, InnoDB 엔진은 모든 세컨더리 인덱스 검색에서 실제 레코드를 읽기 위해서는 반드시 PK를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

즉, 세컨더리 인덱스가 PK의 값을 저장하고 있다. (이중 인덱스 탐색 방식)

1. 세컨더리 인덱스에서 조건에 맞는 PK를 찾는다.

2. 찾은 PK로 클러스터드 인덱스를 검색하여 실제 데이터를 조회한다.

SELECT * FROM users WHERE email = '[e-mail]';

만약, email 컬럼이 인덱스로 설정되어 있으면

1. 먼저 idx_email 인덱스에서 where 조건에 해당하는 id(PK)를 찾는다.

2. 찾은 id(PK) 값으로 프라이머리 인덱스를 통해 실제 데이터를 조회한다.

MyISAM 인덱스 구조와 비교해 보면, 이 구조는 성능이 떨어질 것처럼 보이지만 각각 장단점을 가지고 있다.

• MyISAM 테이블에 저장되는 레코드는 모두 ROWID라는 물리적인 주소 값을 갖는다.

두 엔진의 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아간다는 것이다.

인덱스 키 추가

테이블의 레코드를 변경하는 경우, 인덱스 키 추가나 삭제 작업이 발생한다.

인덱스 키 추가/삭제가 어떻게 처리되는지 안다면 쿼리 성능을 예측하고 주의해야 할 점도 알 수 있을 것이다.

새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라서 새로운 키 값이 즉시 인덱스에 저장될 수 있고 그렇지 않을 수 있다.

저장 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 리프 노드에 저장한다.

리프 노드가 가득 차서 저장할 수 없다면 리프 노드에서 분리(스플릿)이 발생하는데, 이렇게 재조정하는 과정은 상위 브랜치 노드까지 처리 범위가 넓어지기 때문에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.

중요한 것은 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간인 disk I/O이다.

B-Tree 쓰기 작업시 발생하는 디스크 I/O는 아래와 같을 수 있다.

• 새로운 키 삽입시 리프 노드 읽기

• 리프 노드가 가득 차서 스플릿 작업

• 분할된 노드를 디스크에 write

• 상위 브랜치 노드 갱신

이러한 이유로 B-Tree 인덱스는 읽기 작업에 최적화되어 있으며 쓰기 작업은 상대적으로 비용이 많이 발생한다.

따라서 불필요한 인덱스를 만들면 쓰기 성능이 크게 저하될 수 있어, 인덱스 설계 시 이러한 부분들을 고려해야 한다.

인덱스 키 삭제

키 삭제는 간단하다. 키 값이 저장된 리프 노드를 찾아서 마크만 하면 끝이다.

삭제 마킹된 인덱스 키 공간은 그대로 두거나 재활용할 수 있다. 마킹 작업 또한 disk write가 필요해서 이 또한 disk I/O가 필요한 작업이다.

인덱스 키 변경

인덱스의 키 값은 값에 따라 리프 노드의 위치가 결정된다. 그래서 키 값이 변경되는 경우 단순히 키 값만 변경하는 것은 불가능하다.

B-Tree에서 키 값 변경은 먼저 키를 삭제하고 다시 새로운 키 값을 추가하는 방식으로 처리된다. 앞에서 설명한 추가/삭제 작업이 절차대로 처리되기 때문에 이 역시도 disk I/O가 발생한다.

인덱스 키 검색

B-Tree에서 추가/삭제/변경과 같은 무거운 비용을 감당하면서 인덱스를 구축하는 이유는 바로 빠른 검색이다.

루트 노드 → 브랜치 노드 → 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 “트리 탐색” 이라고 한다.

트리 탐색은 select에서만 사용하는 것이 아니라 update, delete를 처리하기 위해 해당 레코드를 먼저 검색해야 하는 경우에도 사용된다.

인덱스 검색은 키 값의 앞부분이 일치하는 경우에 사용할 수 있다. 부등호(<, >) 비교 조건에서도 활용할 수 있지만, 키 값의 뒷부분만을 검색하는 용도로는 사용할 수 없다.

인덱스 검색에서 중요한 것은 키 값의 변형, 즉 조회하려는 데이터가 변형된다면 빠른 검색 기능을 사용할 수 없다. 그 이유는 함수나 연산을 수행한 결과는 인덱스에 존재하는 값이 아니기 때문이다. 그래서 인덱스를 타지 않는 대표적인 경우에는 함수 또는 연산자를 사용하는 경우가 포함되는 것이다.

Q&A

1. 해시 인덱스 대신 B-Tree를 사용하는 이유

• 범위 검색 지원

  • B-Tree는 데이터를 정렬된 상태로 유지하므로 부등호 연산(<, >, between 등)을 효율적으로 처리할 수 있지만, 해시 인덱스는 동등 비교에만 최적화 되어 있다. 범위 검색이나 정렬되지 않은 결과를 가져오기 위해서는 많은 디스크 I/O를 유발할 수 있다.

• 정렬과 순차 접근

  • 해시는 정렬 순서가 보장되지 않아 order by 시 추가 정렬 작업이 필요할 수 있다.

  • B-Tree는 이미 데이터가 정렬되어 있어서 order/group by 등이 효율적이다.

• 부분 검색(Prefix Search)

  • 해시는 완전한 키 값이 존재해야만 검색이 가능하다. (LIKE 'Kim%'같은 검색이 비효율적)

  • B-Tree는 키의 일부분만으로 검색이 가능하다. (LIKE 'Kim%'같은 패턴 검색 효율적)

• 디스크 I/O

  • 해시는 키마다 랜덤한 위치 접근으로 디스크 I/O 많이 발생

  • B-Tree는 하나의 노드에 여러 키를 저장할 수 있는 구조적 특성으로 I/O 효율성을 높이는데 기여