[CS/DB] INDEX

주현·2025년 4월 20일

B+TREE Index

CS

목록 보기

4/8

Index란 무엇인가?

인덱스는 데이터베이스에서 검색의 속도를 향상시키기 위해서 사용하는 자료구조입니다. 책의 색인과 같다.
특정 칼럼을 복사하여 별도의 메모리 공간에 정렬된 상태로 저장하여 관리하기에 추가적인 메모리가 든다.

[ 장점과 단점 ]

장점
- 테이블을 조회하는 속도를 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리해야하기 때문에 추가적인 메모리 공간이 필요하다.
- INSERT,UPDATE등 쿼리에 대해서 추가 적인 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하가 될 수 있다.

만약 DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게된다면, 작업이 있을때마다 인덱스의 크기가 더욱 비대해져갈 것이다. 왜냐하면 UPDATE,DELETE 연산은 기존의 인덱스를 삭제하는 것이 아닌, "사용x" 처리를 한다. 그렇기에 이 연산이 빈번히 발생한다면 실제 데이터보다 인덱스가 훨씬 비대해져서 역으로 성능이 낮아질 수가 있다.

[ 인덱스(index)의 관리 ]

DBMS는 index를 항상 최신의 정렬상태로 유지해야 값을 빠르게 탐색할 수 있다. 그렇기에 인덱스가 적용된 칼럼에 INSERT,DELETE, UPDATE 연산을 진행하게 된다면, 추가적인 연산이 필요하다.

INSERT : 새로운 데이터에 인덱스를 추가해야함.

UPDATE : 기존 인덱스를 사용하지 않음 처리 후, 개인된 데이터에 인덱스를 추가해야함.

DELETE : 삭제하는 데이터의 인덱스를 사용하지 않음 처리 해야함.

이렇듯 추가적인 연산이 필요하다.

[ 인덱스(index)가 좋은 경우 ]

INSERT,DELETE, UPDATE 연산이 없고 조회연산이 많은 곳

규모가 작지않은 테이블

JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼등이 있다.

인덱스의 자료구조

기본적으로 인덱스로 많이 사용되는 B-Tree에 대해서 알아보자

B-Tree

B-Tree는 모든 리프노드가 동일한 레벨에 존재하는 특징을 갖고 있으며, 이진탐색트리는 2개의 자식노드만 가지지만 이는 2개 이상의 자녀 노드를 가질 수 있다.

부모 노드에 저장된 값이 N개라면 그 하위 노드는 최대 N+1개의 노드를 가질 수 있게 된다. 위 사진을 보면 부모 노드에 55,65가 있다면, 자식은 55이하, 55~65, 65이상로 나뉘어져 N+1 노드를 갖게된다.

이러한 특징으로 검색 성능뿐 아니라 이진 탐색트리에 비해 데이터 관리의 효율도 증가하게 됐다.

B+Tree

B+Tree에서 검색 성능을 한층 개선한 자료구조가 B+Tree이다. MYSQL의 InnoDB엔진에서 Index를 관리할때 사용되는 자료구조이다.
이는 리프노드가 연결리스트로 되어있어 B-Tree보다 검색 연산이 빠르며, 범위 검색을 할때 매우 유용하다는 특징이 있다.

B-Tree의 범위 검색

A이상 B이하 범위를 찾아야하는 상황이 있을 경우, A,B의 위치를 찾아야한다. B-Tree에서의 범위검색은 처음 루트 노트로부터 A를 찾아될 것이다. 그리고 B또한 루트 노트로부터 B를 찾아야 한다. 즉, 최상위노드부터 검색하는 과정 2번이 일어나게된다.

B+Tree의 범위 검색

B+Tree는 B-Tree에서 리프노드가 연결리스트로 추가된 자료구조이다. B-Tree와 다르게 A,B중 하나의 위치를 알게된다면 그 후로부터 이어 붙어있는 B까지 빠르게 탐색해서 찾아올 수 있다.

B-Tree VS B+Tree

범위 검색의 내용을 보면 B+Tree가 당연히 유용하다고 적혀있으나, 이에 따른 각각의 장단점이 있다.

메모리 효율 : B-Tree에선 각 노드에 데이터의 주소 뿐 아니라, 식제 데이터로 오름차순으로 정렬되어 있고, B+Tree는 리프노드에만 실제 데이터가 저장되어있습니다. 그렇기에 메모리 효율 측면에서 B+Tree가 좋다.

추가 연산의 효율 : B+Tree는 리프노드간 연결을 나타내는 데이터도 추가적으로 관리해야한다. 그래서 생성,수정,삭제가 일어날때 B-Tree가 더 효율적이다.