B-Tree 인덱스
설명
B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. B-Tree 에는 여러 가지 변형된 형태의 알고리즘이 있는데, 일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree 가 사용된다. B-Tree의 “B”는 Binary가 아니라 Balanced 이다.
구조 및 특성
B-Tree 인덱스를 제대로 사용하려면 B-Tree의 기본적인 구조를 알아햐 한다. B-Tree는 트리 구조의 최상위에 하나의 “루트 노드(Root node)”가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다. 트리 구조의 가장 하위에 있는 노드를 “리프 노드(Leaf node)”라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간의 노드를 “브랜치 노드(Branch node)” 라고 한다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.
데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있다. 많은 사람들이 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것ㄴ으로 생각하지만 그렇지 않다. 만약 테이블의 레코드를 전혀 삭제하거나 변경하지 않고 INSERT만 수행한다면 맞을 수도 있다. 하지만 레코드가 삭제되어 빈 공간이 생기면 그 다음의 INSERT는 가능한 한 삭제된 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT 된 순서로 저장되는 것은 아니다.
대부분 RDBMS의 데이터 파일에는 레코드 특정 기준으로 정렬되지 않고 임의의 순서로 저장된다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장된다. 이는 오라클의 IOT(Index organized table)나 MS-SQL의 클러스터 테이블과 같은 구조를 말한다. 다른 DBMS에서는 클러스터링 기능이 선택 사항이지만, InnoDB에서는 사용자가 별도의 명령이나 옵션을 선택하지 않아도 디폴트로 클러스터링 테이블이 생성된다. 클러스터링이란 비슷한 겂을 최대한 모아서 저장하는 방식을 의미한다.
인덱스틑 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.
B-Tree의 리프 노드와 테이블 데이터 레코드(MyISAM)
B-Tree의 리프 노드와 테이블 데이터 레코드(InnoDB)
MyISAM 테이블의 인덱스와 데이터 파일의 관계를 보여주는데, “레코드 주소”는 MyISAM 테이블의 생성 옵션에 따라 레코드가 테이블에 INSERT된 순번이거나 데이터 파일 내의 위치(Offset)다. MyISAM 스토리지 엔진에서 인덱스의 구조는 ROWID 를 참조. InnoDB 테이블의 인덱스의 데이터 파일의 관계를 보여주는데, InnoDB 스토리지 엔진을 사용하는 테이블에서는 프라이머리 키가 ROWID의 역할을 한다.
두 스토리지 엔진의 인덱스에서 가장 큰 차이점은 세컨터리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법에 있다. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지는 반면 InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다. 그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 못한다. 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색해야 한다. 간단히 생각하면 이 작업으로 인해 InnoDB 스토리지 엔진을 사용하는 테이블은 성능이 떨어질 것처럼 보이지만 사실은 MyISAM 인덱스 구조와 InnoDB 스토리지 엔진을 사용하는 테이블은 성능이 떨어질 것처럼 보이지만 각각의 인덱스 구조는 장단점을 가지고 있다.