[Database] 인덱스(Index)란 무엇인가? : B+Index의 구조

이전에 쿼리튜닝을 공부하면서 인덱스에 대해 살짝 알아봤었다.

쿼리 튜닝에 대하여(기초)

오늘은 인덱스란게 어떻게 데이터 조회 속도를 향상시키는지
그 구조와 종류에 대해 알아보려고 한다.

 

Index 너는 누구인가?

인덱스(Index)란 정확히 무엇인가?

인덱스는 테이블에서 데이터를 빠르게 읽을 수 있도록 도와주는 자료구조 이다.
흔히 책의 목차 정도로 이해하면 될 것이다.

테이블의 특정 컬럼에 대해 별도의 자료구조를 만들어
데이터베이스에서 테이블의 모든 테이블을 검색하지 않고, 원하는 데이터를 빠르게 찾도록 도와준다.

https://mangkyu.tistory.com/96

Index는 포인터 목록이라고 할 수도 있는데, 별도 공간에 Key + RowId의 쌍을 저장한다.
여기서 RowId는 테이블의 행(Row)가 저장된 물리적 주소값이다.

Index는 이런 물리 주소와 key가 저장된 자료구조인 것이다.

Index의 종류

자료구조에 따른 분류

Index 구현을 위해 다양한 자료구조를 사용할 수 있는데,
가장 많이 사용하는 것이 B+Tree이다.

B-Tree / B+Tree Index

이 B+-Tree Index 들을 이해하기 위해서는
B-Tree와 B+Tree 자료구조에 대해 이해해야 한다.

https://zorba91.tistory.com/293

B+Tree는 B-Tree의 변형이다.
B+-Tree는 최상위 Root Node, 중간의 branch Node, 가장 아래 노드인 Leaf Node로 이루어져 있다.

[ B-Tree ]

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

B-Tree는 자식 노드가 2개 이상인 균형 잡힌 트리 구조이다.
파란 부분이 각 노드의 key값이고 빨간부분이 자식을 가리키는 Pointer이다.

key들은 항상 노드 안에서 정렬되어 있고
각 key들의 왼쪽 자식들은 key보다 작은 값을 오른쪽은 큰 값을 가진다.

검색 시에는 루트노드에서 시작해서 key들을 순회하면서 검사한다.
key와 검색할 값의 대소관계를 비교하여 왼쪽 or 오른쪽으로 내려가며 검색하는 방식이다.

만약 원하는 값과 key값이 일치할 시
노드에 저장되어있는 데이터를 꺼내온다.

DBMS의 Index에서 노드의 데이터는 Table의 RowId 또는 row 데이터가 담겨있다.

[ B+Tree ]

B-Tree는 각 노드에 데이터를 저장할 수 있고
각 Leaf 노드 간에 연결이 되어있지 않는 트리이다.

하지만 B+Tree는 최하위 Leaf 노드에만 데이터를 저장한다.
또한 리프 노드들 끼리 Linked List로 연결되어 있다.

리프 노드 외에는 데이터를 저장하지 않기 때문에
메모리를 더 확보할 수 있고

리프 노드들끼리 연결되어 있기 때문에
한 번의 선형탐색만으로 데이터 조회가 가능하다.

 

왜 B+Tree를 사용하는가?

현대의 대부분의 관계형 DBMS(MySQL, Oracle 등) 에서는 B-Tree보다 B+Tree를 사용한다.
그 이유는 범위 검색 시 두 트리의 동작방식을 보면 이해가 갈 것이다.

만약 1에서 5까지 데이터가 있는 트리가 있다고 하자.
여기서 2이상 4이하인 데이터를 조회하려고 한다.

B-Tree의 경우에는

               [ 부모 노드: 3 ]
              /                \
  [ 자식 노드A: 1, 2 ]        [ 자식 노드B: 4, 5 ]

2를 조회하기 위해 자식 노드A까지 내려가서 2를 조회한다.
이후에 3을 조회하기 위해 부모 노드의 3을 조회한다.
4를 조회하기 위해 자식 노드 B로 내려가야 한다.

B+Tree는 루프 노드가 연결되어 있기 때문에

               [ 길잡이 노드: 3 ]
              /                \
  [ 데이터 노드A: 1, 2 ]  ===>  [ 데이터 노드B: 3, 4, 5 ]
                         (옆길 연결)

노드 A에서 2를 조회하고
다음 값인 3을 조회하기 위해 연결된 노드 B로 이동하여 3, 4를 조회한다.

B-Tree는 트리를 역주행(재귀 호출)하여 다시 노드를 읽어야 하기 때문에
더 많은 연산처리가 필요하다.

때문에 대부분의 DBMS에서 B+Tree를 Index에서 사용한다.

 

이러한 트리구조를 사용하기 때문에
Index를 생성한 테이블에서 CUD(Create, Update, Delete) 발생 시 Index 트리도 수정해야 한다.
때문에 CUD의 성능이 떨어지게 된다.

때문에 Index는
조회가 많고 CUD가 잘 일어나지 않는 테이블에 생성하는 것이 좋다.

 

여기까지 B+Tree에 대해 알아보았다.
B+Tree Index 외에도 Hash 함수와 Hash 테이블을 사용하는 Hash Index,
Bitmap을 사용하는 Bitmap Index 등이 있다.

 

Index 생성 방법

오라클을 예시로 Index 생성하는 방법을 보도록 하겠다.

단일 컬럼 인덱스

CREATE INDEX IDX_PROD_NO ON PRODUCT (PROD_NO);

가장 기본적인 Index로 컬럼 1개를 Index로 거는 것이다.

 

복합 컬럼 인덱스

CREATE INDEX IDX_PROD_NO_PRICE ON PRODUCT (PROD_NO,PRICE);

2개 이상의 컬럼을 조합하여 생성하는 인덱스이다.

복합 컬럼 인덱스에서는 지정한 컬럼 순서대로 정렬하여 트리를 생성한다.
이 예시에서는 PROD_NO를 우선 정렬하고 동일한 경우 PRICE로 정렬한다.

첫번째 컬럼을 기준으로 정렬되는 구조이므로
where 절에 첫번째 컬럼이 누락되면 Index를 타지 못한다.

 

 

유니크 인덱스

CREATE UNIQUE INDEX IDX_PROD_NM ON PRODUCT (PROD_NAME);

중복값을 허용하지 않는 인덱스이다.

일반 인덱스는 KEY+ROWID로 저장되어
KEY가 같아도 ROWID가 다르면 별도 행으로 구분되어 저장된다.

때문에 검색한 KEY값을 만나도 또 같은 KEY가 있을 수 있기 때문에
옆 칸을 확인하는 연산을 수행한다.

하지만 유니크 인덱스는 중복값이 없기 때문에
KEY를 찾으면 해당 데이터를 반환한다.

✅ 유니크 인덱스에 중복 KEY를 INSERT 하려고 할 경우에는 어떻게 될까?
유니크 인덱스가 적용된 컬럼에 중복된 값을 INSERT 하려고 시도하는 경우에는
무결성 제약 조건에 위배되어 INSERT 명령어가 Rollback된다.

때문에 유니크 인덱스는 PK값에 지정하는 것을 추천한다.

 

지금까지 Index의 정의와
B+Tree Index의 구조에 대해 알아보았다.

 

다음 스터디에서는 파티션 테이블과
파티션 테이블에서의 인덱스 동작방법에 대해 알아보고 싶다.

 

참고자료

[자료구조] 그림으로 알아보는 B-Tree