인덱스 (Index)
인덱스(Index) 란 데이터베이스에서 원하는 데이터를 빠르게 검색하고 엑세스하기 위해 사용되는 자료구조입니다. 정확히는, 이 자료구조 내에서 각 단위를 인덱스라고 지칭하는 것이며, 여러 종류의 인덱스 중에서 추후 살펴볼 노드(node) 가 데이터 레코드(실제 데이터) 를 포인터로 가리키는 형태입니다. 이때 대부분의 DBMS 에서는 인덱스에 대한 저장방식으로 B-Tree 와 B+Tree , 그리고 Hash 자료구조를 채택하고 있습니다.
각 인덱스는 데이터 레코드의 특정 컬럼을 타킷으로 해서, 컬럼의 값과 해당 레코드가 저장된 주소(포인터)를 key-value 쌍으로 저장하고 있습니다.
정확히는, 이 자료구조 내에서 각 단위를 인덱스라고 지칭하는 것이며, 여러 종류의 인덱스 중에서 추후 살펴볼 노드(node) 가 데이터 레코드(실제 데이터) 를 포인터로 가리키는 형태입니다. 이때 대부분의 DBMS 에서는 인덱스에 대한 저장방식으로 B-Tree 와 B+Tree , 그리고 Hash 자료구조를 채택하고 있습니다.
조회(select) 를 위한 최적화 구조
인덱스는 B+ Tree 와 같은 저장방식을 취함으로써 항상 정렬된 상태를 유지합니다. 반면 인덱스들이 가리키는 데이터 파일의 레코드들은 별도의 순서 정렬없이 데이터가 유입되는대로 곧바로 저장합니다. 떄문에 DBMS 상에서 인덱스는 데이터의 저장(insert, delete, update)의 성능을 희생한 대신에, 조회(select) 의 성능을 최적화한 구조라고 볼 수 있습니다.
B-Tree Index
B-Tree 는 이진트리와 달리 자식 노드를 여러개 가질 수 있는 균형잡힌(Balanced) 트리 구조입니다. 가장 최상위에는 하나의 루트 노드(root node) 가 존재하며, 맨 하위 계층에는 리프 노드(leaf node) 가 존재하며, 이들 사이에 있는 중간노드로 브랜치 노드(branch node) 가 존재합니다. 여기서 key 값이란, 실제 데이터 레코드의 key 값을 의미하는 것으로, 각 레코드를 식별할 수 있는 (중복되지 않는) 값을 지닌 컬럼의 값을 의미합니다. 대표적으로 프라이머리 키(primary key) 값이 이에 해당되겠죠.
바로 뒤에 살펴볼 B+ Tree 와 다른점은 리프노드 에서 가장 큰 차이점을 보입니다. B+ Tree 의 리프노드는 각 노드끼리 링크드리스트로 연결된 형태이나, B-Tree 는 그렇지 않습니다.
B+ Tree Index
B- Tree 와의 차이점 : 리프노드
B+ Tree 는 앞서 살펴본 B- Tree 에서 응용된 구조로, 몇가지 특징에서 차이점을 보입니다. 우선 모든 노드에서 레코드에 대한 primary key 값을 저장하고 있는 B-Tree 와 달리, 오직 리프 노드에서만 실제 레코드에 대한 primary key 값을 저장하고 있습니다.
여기서 리프 노드에서는 실제 레코드를 가리키기 위한 포인터를 저장하고 있는것처럼 묘사되었는데, 이는 비클러스터링 인덱스(Non-Clustering Index) 에 해당하는 경우입니다.
1. 더블리 링크드리스트
또한 같은 깊이(depth) 에 존재하는 노드들은 서로 링크드리스트 구조로 연결된 형태를 취합니다. 이에따라, 리프 노드끼리도 더블리 링크드리스트로 연결된 구조를 지닙니다.
여기서 바로 B+ Tree 의 강점이 드러납니다. 레인지 스캔(Range Scan) 이나 풀 스캔(Full Scan) 수행하는 경우 B- Tree 보다 훨씬 유리하다는 특징이 있죠. 이들을 수행하는 경우 O(logbN) 타임에 루트부터 시작해서 리프까지 도달한후에, 특정 리프에서 부터 시작해서 링크드리스트를 따라 넘어가면서 여러 리프노드들을 순차적으로 선형탐색 방식으로 스캔하면 됩니다.
그러나 B- Tree 의 경우 링크트리스트로 연결된 구조가 아니기 때문에, 이를 수행할 경우 모든 노드에 대해 일일이 스캔을 수행해야한다는 번거로움이 있습니다.
2. 더 많은 인덱스를 담을 수 있는구조
또한 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있게됩니다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아지게 되는 것이죠. (cache hit를 높일 수 있음)
B+ Tree 레코드 테이블
인덱스는 테이블의 key 컬럼만 저장하고 있기 떄문에, 레코드에서 원하는 나머지 컬럼들 (Secondary Index) 을 조회하는 경우 데이터 파일에서 해당 레코드를 찾아야합니다.
이때 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을때는 데이터 파일에서 즉시 조회하지 못합니다. 이 이유는 데이터 파일 또한 B+ Tree 형태로 구현되어있기 때문이죠.
데이터 파일의 B+ Tree 구조에서, 인덱스(리프 노드)에 저장되어 있는 key 값과 일치하는 레코드를 찾아서 O(logbN) 타임에 다시 내려가서 원하는 레코드를 조회해야하는 방식입니다.
즉, 정리하자면 InnoDB 스토리지 엔진에서는 모든 세컨더리 인덱스 검색해서 데이터 레코드를 조회하기 위해 반드시 key 값을 저장하고있는 B+ Tree를 다시 한번 탐색해야 합니다.
B+ Tree 의 인덱스 key 연산
테이블의 레코드를 저장하거나 변경하는 경우 인덱스의 key 값이 추가되거나, 삭제되는등의 연산이 발생할겁니다. 인덱스의 key 값 추가나 변경, 삭제등이 어떻게 처리되는것이 이해해두면 쿼리의 성능을 예측하기 쉬워질겁니다.
인덱스 key 값 추가
새로운 key 값이 저장되기 위해선, 루트에서 부터 시작해서 범위 값을 대소비교하면서 삽입될 리프 노드에 찾아가서 삽입되면 됩니다. 이때 주의할점은 삽입되어야할 리프 노드가 key 값이 꽉 차서 더이상 저장할 수 없는 경우, 리프 노드가 split 되어야한다는 특징이 있습니다.
split 될때 새롭게 생긴 오른쪽의 노드의 맨 앞 원소는 두 리프노드의 부모 노드에 삽입되어야 한다는 과정이 있는데, 이때 부모 노드에서도 split 을 해야하는 상황이 발생할 수 있습니다. 최악의 경우에는 이러한 split 의 전파가 루트 노드까지 올라간다는 특징 때문에, B+ Tree 의 key 값 추가는 비용이 많이 드는것으로 알려져있습니다.
이러한 단점 때문에 InnoDB 엔진에서는 INSERT 문이 실행되면 필요에따라 인덱스의 key 추가 작업을 지연시켜서 나중에 한번에 처리된다고 합니다. 하지만 primary key 나 unique key 인덱스의 경우는 중복 체크가 필요하기 때문에 즉시 B+ Tree 에 추가하거나 삭제한다고 합니다.
인덱스 key 값 삭제
삭제는 꽤나 간단합니다. 리프 노드중에 해당 key 값이 저장되어 있는 곳을 찾아내서 해당 key 값을 인덱스에서 삭제시켜주면 끝입니다. 이때 삭제된 공간은 추후 재활용된다는 가정하에, 그대로 냅둡니다.
몰론 이때 삭제된 key 값이 가리키는 실제 레코드 데이터는 데이터 파일에서 삭제되지 않습니다. 실제 레코드는 그저 인덱스를 보유하지 않는 상태가 되는것입니다.
인덱스 key 값 변경
인덱스의 key 값은 해당 key 값에따라 리프 노드의 위치가 결정되므로, 단순히 인덱스상의 key 값만 변경하는 것은 불가능합니다. 먼저 기존 key 값을 삭제 연산을 진행한 후, 새로운 key 값을 추가 연산을 진행하는 형태로 처리됩니다. 이때 InnoDB 엔진에서는 이 작업을 모두 체인지 버퍼(Change Buffer) 를 통해 지연 처리될 수 있다고합니다.
인덱스 key 값 조회
key 값을 조회하는 것은 여러 방식이 있겠지만, 여기서는 하나의 특정 key 값을 조회하는 경우를 가정하겠습니다. 앞서 말했듯이, 이 연산은 루트에서부터 시작해서 특정 리프에 있는 key 값을 조회해오면 끝입니다. 이 과정이 O(logbN) 에 수행된다는 것이죠.
이때 주의할 점은 변형된 key 값 에 대해서는 B+ Tree 의 장점을 누릴 수 없다는 것입니다. 인덱스의 key 값에 변형이되면 해당 key 값은 B+ Tree 인덱스에 존재하지 않는 값이기 떄문이죠. 따라서 함수나 연산등으로 수행한 결과를 정렬하거나 검색하는 작업은 B+ Tree 의 인덱스에 존재하는 대상이기 때문에 주의해서 사용해야 합니다.