[DataBase] Index란?

책에서 우리는 원하는 단어를 찾을 때 우리는 목차를 볼 때도 있고 단어를 정리한 페이지를 찾을 때도 있다. 우리는 이를 활용해서 시간을 절약할 수 있고, 여기서 목차는 인덱스라 말한다. 이와 같은 인덱스는 자료를 찾을 때 시간을 절약할 수 있게 만든다. 한편으로는 책의 페이지 수가 늘어난다는 점이다. 이제는 인덱스에 대해 이해가 조금은 갈 것이다.

 

탐색 알고리즘에서 우리는 해쉬 테이블과 이진 트리를 접했다. 이진 트리는 자식이 2개 이하인 트리를 말하고 root 노드가 하나 있고 그 밑에 하위 노드들이 뿌리처럼 가지고 있다. 해쉬 테이블은 해쉬 함수를 통해 주소 값을 참조하고 새로운 테이블을 만들어 관리하는 식이다. 인덱스는 이러한 원리로 동작하게 된다.

 

해쉬 테이블 (Hash Table)

해쉬 테이블은 엔트리 구조로 저장하는 자료구조 중 하나로 빠르게 데이터를 조회 할 때 사용하고 non-clustered Index 의 구조로 사용 한다.

 

 

해시 함수를 사용하여 얻은 주소 값에 데이터를 저장하는 식으로 검색하는데 시간을 절약하게 해준다.

하지만 해쉬 테이블은 = 이퀄 연산에만 특화 되어 있기 때문에 부등호 연산 <, > 이 자주 사용되는 검색은 적합하지 않다.

 

B Tree (Balanced Tree)

이진 트리와 다르게 자식 노드가 2개 이상을 가진 트리 구조고 정렬이 된 데이터로 Clustered Index 의 구조로 사용되고 있다.

 

 

각 노드는 항상 정렬된 상태이며 데이터와 데이터 사이의 범위를 이용해서 자식 노드를 가진다.

 

 

데이터를 저장하는 기본 단위는 페이지 또는 블록이라 하며 B Tree의 동작은 수직으로 조건에 맞는 노드들의 페이지를 탐색하고 수평으로 조건에 맞는 마지막 리프 노드에서 레코드들을 탐색한다.

 

Scan

위의 2가지 해쉬 테이블과 B Three 방식으로 Index가 동작하는 것을 알 게 되었다. 기존에 우리는 인덱스를 타지 않는 경우 찾을 테이블에서 조건에 맞는 데이터를 Full Scan 으로 찾아야 했다. 인덱스를 타면 조건에 맞는 데이터를 찾을 시에 멈추고 디스크에 올리는 방식이므로 Range Scan 이라 한다.

 

Index를 언제 타면 좋을까?

자주 사용되는 컬럼으로 select from where절을 사용할 때 효율적이다.

• 카디널리티가 높은 것
  • 분별력있고 고유값인 컬럼
  • 종류의 수가 많은 컬럼
  • where 절과 orderBy 절에 많이 등장하는 컬럼

자주 사용되는 컬럼이 별도의 테이블로 정렬이 되어 관리를 해서 메모리를 내줘야 하지만 Full Scan을 하는 방식보단 Range Scan으로 하는 것이 시간과 비용을 절약할 수 있게 도움을 준다.

 

Composite Index (결합 인덱스)

• select 절에 자주 등장하는 요소를 결합하여 Index 로 설정한다.
• where 절에서 이퀄조건으로 많이 쓰이는 요소들을 Index 로 설정한다.

 

Index의 단점은?

insert, update, delete 에는 비효율적이다. 인덱스는 정렬이 되면서 데이터가 저장이 된다.

• insert

수 많은 인덱스가 있는 테이블에 insert를 하면 새로운 데이터가 자리를 찾아 데이터가 저장되고 순차적으로 뒤에 있는 데이터들은 밀리면서 오버헤드가 발생한다.

또한 인덱스는 domain의 테이블과는 별도로 테이블이 생성이 되며 메모리 낭비가 될 수 있다. 인덱스의 테이블을 관리하기 위해 약 10%에 해당하는 저장공간이 필요하다.

• update

인덱스는 update라는 개념이 없고 기존의 데이터를 사용 안함으로 표시하고 새로운 데이터를 추가하는 식이다.

• delete

인덱스를 삭제하는 것이 아니라 사용안함을 표시하기 때문에 메모리 낭비가 있다.

 

 

 

 

 

 

https://www.youtube.com/watch?v=9ZXIoh9PtwY&ab_channel=우아한Tech

https://www.youtube.com/watch?v=NkZ6r6z2pBg&ab_channel=우아한Tech