[DB] INDEX에 대해서

728x90

INDEX란?

RDBMS에서 대용량의 데이터가 존재할 때, 특정 데이터를 검색하기 위해 테이블을 FullScan하는것이 아니라 Range Scan을 통해 빠르게 검색할 수 있도록 도와주는 자료구조이다.
정렬 된 구조로 ROWID가 존재하기 때문에 별도의 정렬이 필요없어서 ORDER BY를 사용하는것보다 훨씬 효율적이다.
데이터를 찾은 후 ROWID를 이용하여 테이블 레코드를 찾아간다.

인덱스의 자료구조

인덱스의 자료 구조 종류는 다양하게 존재한다.
그중에서 B-Tree구조 , B+Tree , B*Tree 구조와 HashTables 구조를 많이 사용한다.

▶ B-Tree 구조

자식의 노드 개수가 2개이상인 트리구조를 뜻한다.

B-Trees는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 균형 이진 트리의 확장판이라고 할 수 있다.

하나의 노드안에 여러 정보들로 구성될수 있다.
n개의 정보들로 구성되어있으면 N차 B-Tree(자식노드가 최대 N개임)로 불린다.
하나의 블럭안에 여러 데이터들을 저장 할 수 있어 많은 데이터베이스에서 사용한다.

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

www.cs.usfca.edu

위의 링크는 B-Tree의 과정을 나타내는 사이트이다.

특징

LeaftBlock의 깊이가 모두 동일하게 균형(Balance)잡혀있다.
Key-Value값으로 구성되어있고 Key값을 기준으로 오름차순 정렬되어있다.
자료는 중복되지 않는다.
RootNode는 본인이 LeafNode가 되지않는 이상 2개이상의 자식 노드를 가진다.
탐색을 위해서는 노드를 찾아 이동해야한다. (단점)
구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성되야 한다. (단점)

▶ B+Tree 구조

B-Tree를 확장한 구조로 B-Tree구조와는 다르게 Branch Node는 Value에 대한 정보가 없고 Key값만 존재한다. (인덱스 노드= 다음노드를 가리키고 있는 Pointer 주소 존재)

말단 노드인 Leaft노드에서만 Value를 관리한다. (데이터 노드 = 실제 데이터 )

B+Tree구조는 Branch Node에 Value가 존재하지 않기때문에 B-Tree에 비해 차지하는 메모리가 적다.

B-Tree 단점을 해소하고자 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling node는 연결리스트 형태로 이어져 있다.

Leaf Node들은 LinkedList구조로 서로를 참조하고 있기때문에 B-Tree에 비해 노드 순환이 쉽다.

https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+ Tree Visualization

www.cs.usfca.edu

위의 링크는 B+Tree의 과정을 나타내는 사이트이다.

특징

데이터 노드의 자료는 정렬 되어있다.
모든 leaf node는 같은 레벨에 있다.
모든 leaf node는 연결리스트로 연결되어 있다.
value를 찾기위해서는 말단 노드까지 이동해야한다.

▶ B*Tree 구조

노드의 추가적인 생성과 연산을 최소화하기 위하여 B-Tree에서 확장한 개념이다.

특징

노드의 약 2/3이상이 채워지는 구조이다.
노드가 꽉 차면 새로운 노드를 생성(분리)하는 것이 아닌 키와 포인터를 재배치하여 다른 형제 노드로 옮기는 구조이다.

▶ HashTables 구조

Key-Value 형태로 데이터를 저장하는 자료구조이다.

데이터 탐색 시 해시 함수(Hash Function)를 이용해 Key에 해당하는 고유 index 값을 구한다.

https://en.wikipedia.org/wiki/Hash_table

index를 이용하여 배열에 저장된 value에 접근하기 때문에 해시 테이블의 평균 시간복잡도는 O(1)이다.

내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 제공한다.

DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적이다.

해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

그러한 이유로 해시가 등호(=) 연산에만 특화되어 있다.

특징

해시함수를 사용한다.
빠른 검색 속도를 지니고 있다.
등호(=) 연산에만 특화되어있기때문에 해시 테이블의 사용이 제한적이다. (단점)

인덱스의 장단점

▶ 장점

테이블에서 검색과 정렬 속도를 향상시킨다.
질의문에서 그룹화 작업 속도를 향상시킨다.

▶ 단점

데이터베이스 공간을 차지하기때문에 추가적인 저장 공간이 필요하다.(10%)
인덱스 관리를 위한 추가 작업=공수가 필요하다.
INSERT는 새로운 데이터가 추가되면서 기존 인덱스 페이지에 저장되었던 탐색 위치가 수정되므로 효율이 좋지 않다.
DELETE 경우 기존 테이블에서는 그냥 레코드를 삭제하고 그 공간을 다른 레코드가 사용할 수 있지만 인덱스 테이블은 사용 안함 표시만 하고 자리를 그대로 차지한다.
데이터 조회(SELECT)를 제외한 모든 동작,즉, INSERT / UPDATE / DELETE 성능에 영향을 미친다.
데이터 변경(Insert, Delete , Update)이 자주 일어나는 테이블 혹은 컬럼에는 인덱스로 설정하면 안된다.

THE END ... 추가적으로

RDBMS란 행과 열로 이루어진 각각의 테이블을 참조하여 서로 종속되어있는 관계를 표현한 관계형 데이터베이스
ROWID란 데이터베이스내의 주소값을 저장하고 있는 공간
RangeScan이란 특정값을 찾다가 해당 범위를 넘어서는 값을 만나면 멈춘다.
균형 이진트리란 leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리를 뜻하므로 균형이 깨지면 새로운 노드를 생성해 균형을 맞춘다.