8.인덱스 - B-Tree Index

2022.12.14 - [RealMySQL] - 8.인덱스 - 인덱스란?

8.인덱스 - 인덱스란?

전 포스트에 이어서 B-Tree 인덱스에 대해서 자세히 알아보도록 하겠습니다.

 

B-Tree Index(Balanced Tree Index)

B-Tree는 컬럼의 원래 값을 변경하지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지됩니다.

전문 검색과 같은 특수한 요건이 아닌 경우를 제외하고 대부분의 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘입니다.

 

B-Tree의 구조는 트리 구조의 최상위에 루트 노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태입니다. 트리 구조의 가장 하위에 있는 노드를 리프 노드라 하고 중간의 노드를 브랜치 노드라고 합니다.

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리가 되는데 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있습니다.

B-Tree 구조

InnoDB vs MyISAM

InnoDB B-Tree(왼쪽)와 MyISAM B-Tree(오른쪽)

MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소 즉 실제 데이터 파일의 주소를 가지는 반면 

InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가집니다.

 

그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 못하고 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후 실제 데이터를 찾게 됩니다. 이러한 방법 때문에 InnoDB 스토리지 엔진을 사용하는 테이블은 성능이 많이 떨어질 것처럼 보이지만 그렇지 않습니다. 두 엔진의 인덱스 장단점에 대해서는 8.8 클러스터링 인덱스에서 자세히 알아보도록 하겠습니다.

 

B-Tree 인덱스 키 추가

B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색한 후 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree에 저장합니다.

 

리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데 이는 상위 브랜치 노드까지 영향을 줄 수 있습니다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기작업에 비용이 많이 듭니다.

 

InnoDB 스토리지 엔진은 인덱스의 키 추가 작업을 지연시켜 다른 스토리지 엔진보다 효율적으로 처리가 가능하지만 프라이머리 키나 유니크 인덱스의 경우 중복체크를 해야되기 때문에 즉시 B-Tree에 추가하거나 삭제하는 작업을 하게 됩니다.

 

B-Tree 인덱스 키 삭제

해당 키 값이 저장된 리프 노드를 찾아서 삭제 마킹을 하게 됩니다. 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용 할 수 있습니다. 인덱스 키 삭제로 인해 삭제 마킹 작업도 디스크 쓰기가 필요하므로 디스크 I/O 작업이 필요한데 InnoDB 스토리지 엔진에서는 이 작업도 버퍼링 시켜 효율적으로 처리가 가능합니다.

 

B-Tree 인덱스 키 변경

인덱스 키 값은 그 값에 따라서 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스상의 키 값만 변경하는 것이 불가능하고 인덱스 키 값을 삭제하고 다시 새로운 인덱스 키 값을 추가하는 형태로 처리가 됩니다.

 

B-Tree 인덱스 키 검색

INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따른 추가 비용을 감당하면서 인덱스를 추가하는 이유는 빠른 검색을 위해서 입니다. B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데 이 과정을 트리 탐색이라 합니다.

 

트리 탐색은 SELECT 작업 외에도 UPDATE나 DELETE 작업을 처리하기 위해 해당 레코드를 먼저 검색해야 할 경우에도 사용됩니다.

 

B-Tree 인덱스를 이용한 검색은 100% 일치, 값의 앞부분(Left-most part)만 일치 할 때 사용이 가능하고 부등호 비교조건에서도 인덱스를 사용이 가능하지만 인덱스를 구성하는 키 값의 뒷 부분만 검색하는 용도로는 사용이 불가능합니다.

또한 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에도 B-Tree 인덱스 키 검색을 사용할 수 없습니다. 즉 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없습니다.

 

B-Tree 인덱스 사용에 영향을 미치는 요소

B-Tree 인덱스는 인덱스를 구성하는 컬럼의 크기나 레코드의 건수, 유니크한 인덱스 키 값의 개수등에 의해 검색이나 변경 작업의 성능이 영향을 받습니다.

 

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(page)라 합니다.

innodb_page_size 시스템 변수를 이용해 페이지 사이즈 변경이 가능하며 기본 값은 16KB입니다.

 

B-Tree의 자식 노드의 개수는 인덱스 페이지 크기와 키 값의 크기에 따라 결정되는데 인덱스 페이지 사이즈가 16KB이고 인덱스 키가 16byte라고 가정하면 밑의 사진 처럼 인덱스 페이자가 구성되게 됩니다. 

인덱스 페이지 구성

인덱스 페이지당 몇개의 키를 가질 수 있는지 계산해보면 16*1024 / (16 + 12) = 585로 총 585개의 키를 가질 수 있습니다.

만약 인덱스 키 값의 크기가 32byte로 증가하게 된다면 372개의 키를 가질 수 있게되는데 이 경우 요청으로 들어온 SELECT 쿼리가 레코드를 372개 보다 많이 읽어야 하는 쿼리라고 가정을 한다면 최소한 2번 이상 디스크로부터 읽어야 하기 때문에 인덱스 키 값이 작을 때 보다 비효율적으로 데이터를 찾게 됩니다. 즉 인덱스 키 값이 커지면 트리의 깊이가 깊어지고 디스크로부터 읽어야하는 횟수가 늘어나는데 그만큼 느려진다는 것을 의미합니다. 또한 인덱스를 캐시해두는 InnoDB의 버퍼 풀이나 MyISAM의 캐시 영역은 크기가 제한적이기 때문에 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어들어 메모리의 효율이 떨어지는 결과를 가져오게 됩니다.

 

인덱스 사용에 영향을 미치는 요소 중 선택도(기수성)가 있는데 인덱스에서 선택도(selectivity) 또는 기수성(cardinality)은 거의 같은 의미로 사용되며 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미합니다. 전체 인덱스 키 값 100개 중 유니크 한 키가 10개라면 기수성은 10 입니다. 기수성이 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리됩니다.