B-Tree Index (1)

들어가며

지난 글 Index 에서는 인덱스의 특징과 분류에 대해 알아보았다.

이번 글에서는 다음 네 부분에 대해 다루겠다.

 

(1) B-Tree Index의 구조

(2) Index를 통한 레코드 읽기 방법

(3) Index 추가/삭제/변경

(4) Index를 이용한 검색

 

알아보기

B

B-Tree의 B는 무엇의 약자일까?

Binary 라고 생각하기 쉽지만, B-Tree는 이진트리가 아니다.

여기서 B는 'Balanced'의 약자이고, B-Tree의 자식노드 개수는 가변적이다.

B-Tree Index는 column 값을 변경하지 않고 저장해 정렬된 상태로 유지한다는 데에서, Balanced의 의미를 유추할 수 있다.

 

구조

(1) Root Node

(2) Branch Node

(3) Leaf Node : 레코드의 실제 주소를 갖고 있다.

 

B-Tree의 노드는 '페이지' 단위를 기준으로 구분하며 루트노드, 브랜치노드, 리프노드 셋으로 나뉜다.

유의할 점은 루트노드와 리프노드는 항상 존재하지만 브랜치노드는 없을 수도 있다는 것이다.

 

Index로 레코드 읽기

인덱스를 통해 레코드를 읽는 방법에 대해 알아보기 전에 리프노드에 저장되는 값에 대해 알아보자.

MyISAM 스토리지 엔진

MyISAM 테이블에 저장되는 레코드는 물리 주소값인 ROWID를 갖는다.

따라서 Primary Key와 Secondary Index도 모두 ROWID를 포인터로 갖는다.

 

MyISAM 스토리지 엔진의 인덱스를 통해 레코드를 읽을 때에는,

Index가 물리주소인 ROWID를 가지므로 해당되는 데이터 파일을 바로 찾을 수 있다.

 

InnoDB 스토리지 엔진

InnoDB 테이블에서는 PK가 ROWID의 역할을 하기 때문에 논리 주소를 갖는다고 할 수 있다.

 

InnoDB 스토리지 엔진에서 인덱스로 원하는 레코드를 읽기 위해서는,

Primary Key를 한 번 더 검색해 PK의 리프노드에 있는 레코드를 읽어야 한다.

 

차이

InnoDB 스토리지 엔진은 PK를 한 번 더 검색해야 한다고 했으므로 MyISAM 스토리지 엔진을 사용하는 것이 더 빠르다고 생각할 수 있다.

하지만 각각 장단점이 있다.

이 부분은 InnoDB 스토리지 엔진에서만 지원하는 클러스터링 인덱스를 알면 이해할 수 있는데,

이 개념은 추후 더 자세히 다룰 것이므로 여기서는 간단히 알아보고 넘어가겠다.

 

클러스터링 인덱스

Primary Key 값이 비슷한 레코드끼리 묶어서 저장하는 것이다.

즉 PK 값에 의해 레코드의 물리적 저장 위치가 결정된다는 것이다.

InnoDB 스토리지 엔진에서는 항상 클러스터링 인덱스로 저장되는데, 따라서 PK 기반의 검색이 매우 빠르다는 장점이 있다.

(그렇기 때문에 PK로 한 번 더 검색하더라도 성능 상 큰 손해가 없는 것이다.)

 

Index 추가

B-Tree Index는 항상 값이 정렬된 상태로 유지되기 때문에 Index가 추가되어야 할 때 비용이 크다.

Index를 추가할 때에도 스토리지 엔진에 따라 추가된 Index가 저장되는 시기가 다르다.

 

MyISAM 스토리지 엔진

추가 내용이 디스크에 즉시 저장된다.

 

InnoDB 스토리지 엔진

지연 처리가 가능하다. 이 때 체인지 버퍼*를 이용한다.

만약 추가할 Index가 Primary Key 또는 Unique Index일 경우 중복 검사가 필요하므로 즉시 저장된다.

 

과정

(1) 추가될 값을 이용해 저장될 위치를 검색한다.

(2) 위치가 정해지면 값, 주소를 leaf node에 저장한다.

(2)-1. 만약 남는 leaf node가 없다면 leaf node split이 필요해진다.

           이 때 상위 노드까지 처리 범위가 되므로 쓰기 작업에 비용이 커진다.

 

체인지 버퍼

InnoDB에서는 지연 처리가 가능하다.

추가/변경/삭제해야 하는 Index 페이지가 버퍼 풀에 있으면 즉시 추가/변경/삭제하지만, 디스크로부터 페이지를 읽어와서 작업해야 할 경우 이를 즉시 처리하지 않고 임시 공간에 두고 사용자에게는 바로 결과를 반환한다. 이 때 이용되는 임시 공간이 체인지 버퍼다.

체인지 버퍼에 있는 레코드 조각은 백그라운드 스레드에 의해 병합된다.

 

Index 삭제

삭제를 위해서는 leaf node에 marking해주면 된다.

marking 이후에는 방치되거나 재활용될 수 있는데, mark 작업을 위해서는 역시 I/O가 필요하다.

InnoDB 스토리지 엔진에서는 지연처리가 가능하다.

 

Index 값 변경

값을 이용해 저장될 위치를 결정하기 때문에 값이 변경될 경우 위치를 다시 정해야 한다.

따라서 Index를 먼저 삭제한 후 새 키를 추가하는 방식으로 변경을 지원한다.

변경에 대해서도 InnoDB 스토리지 엔진에서는 지연처리가 가능하다.

 

Index 검색

트리탐색

B-Tree 루트노드부터 시작해 브랜치노드 > 리프노드 순으로 탐색하는 것을 말한다.

 

B-Tree의 특징

B-Tree는 왼쪽 값을 기준으로 오른쪽 값을 정렬한다.

따라서 100% 일치하거나 앞부분이 일치하는 경우에 한해 커버할 수 있으며,

뒷부분을 조건으로 검색할 경우 인덱스를 이용할 수 없다.

 

예를 들어 다음 쿼리에서는 id 컬럼으로 인덱스를 구성했다고 하더라도 인덱스를 사용할 수 없다.

앞부분이 아닌 뒷부분의 일치를 조건으로 했기 때문이다.

SELECT id
FROM test
WHERE id LIKE '%eath%'

 

B-Tree는 값을 변경하지 않고 저장한다.

키 값을 변경한 후 비교하는 경우 B-Tree 인덱스를 이용한 빠른 검색이 불가능하다.

 

예를 들어 다음 쿼리에서는 created_at이 인덱스로 등록되어 있더라도 인덱스를 사용할 수 없다.

변경을 가한 인덱스 값은 B-Tree에 존재하지 않기 때문이다.

SELECT id
FROM test
WHERE DATE(created_at) < NOW() - 2