인덱스 (Index)

해당 페이지에서는 DB 에서 쓰이는 인덱스 개념에 대해서 알아본다.

(참고 사이트)

itholic.github.io/database-index/,

ko.wikipedia.org/wiki/%EC%9D%B8%EB%8D%B1%EC%8A%A4_(%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4)

swconsulting.tistory.com/381

 

velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

 

www.guru99.com/indexing-in-database.html (그림출처)

 

blogs.oracle.com/timesten/what-is-the-best-timesten-index-for-my-oltp-application

 

인덱스는 말그대로 색인을 뜻하며 책의 색인을 생각해도 된다. 우리가 책에서 생각하는 메인 주제가 어디 페이지에
기록되어 있다면 그 페이지를 통하여 찾고 싶은 주제를 쉽게 찾을 수 있다는 것을 생각해보자.
이와 같이 인덱스는 데이터베이스의 작업속도를 높히기 위하여 도입된 개념이다.

인덱스는 아래와 같이 나뉘어져 있다.

출처 : https://www.guru99.com/indexing-in-database.html

인덱스의 Main Stream 은 크게 Primary 와 Secondary 로 나뉘어 지며 각각의 특성은 아래와 같다.

 

Primary Index

 

고정된 두개의 필드값으로 구성된 인덱스다. 각각 실제 데이터를 조회시 사용할 정렬된 메인 키워드 데이터와 이에 대한 실제 데이터가 기록된 블록을 찾기 위해 사용할 주소값을 보관 하고 있다. 클러스터 인덱스 (Clustered Index) 와 거의 동일 개념이라서 클러스터 인덱스라고도 한다. (단, 이는 특정 RDBMS 에서는 차이가 있음을 들어 완전히 같지는 않다는 의견들이 있다. 그러나 동작 메커니즘은 동일하기 때문에 특정 차이가 있는 RDBMS 이외의 DB 에서는 동일 개념으로 본다.)

특정 나열된 데이터들을 일정 기준으로 정렬해주는 인덱스다. (ex : 영어사전)

단순 색인을 추가하는 개념과는 다르게 숫자나 알파벳등의 순서대로 데이터 자체를 재배열하는 특징이 있다.

한개의 테이블에 한개씩만 만들 수 있다 (ex : Primary Key)

인덱스는 생성 시 데이터들의 배열정보를 따로 저장하는 공간을 사용하나
(책의 색인 페이지가 따로 있는것과 같은 원리) 클러스터 인덱스는 따로 저장하는 정보공간을 적게 사용하면서테이블 공간 자체를 활용한다. (실무적으로 테이블의 크기를 알아 볼 때, 자체 테이블 크기 및 이와 관련된 인덱스 공간등을 추가로 확인하는 이유다.)

 

아래 그림과 같이 클러스터 인덱스는 root page (node) 와 root page 의 주소값을 받아서 실제데이터를 보관하는 data (혹은 leaf) page (node) 가 있다 (아래에 후술 하겠지만 non cluster 는 root, leaf, data page 가 나뉘어져 있다.)

 

Primary 인덱스는 Dense Index 와 Sparse Index 로 나뉜다.

 

• Dense Index
  
  
  • 데이터 작업에 사용할 모든 키워드 데이터에 주소값이 배정된 형태다.
    
    
  • 모든 데이터에 주소값이 있으므로 데이터 조회 시, 빠른 조회가 가능하다.
    
    
  • 하지만, 모든 데이터에 주소값이 필요함에 따라 데이터가 추가 될 시 이에따른 추가 주소배정 공간이 필요하다.
    
    

 

• Sparse Index
  
  
  • Dense Index 의 단점인 데이터와 주소값의 1:1 대응을 해결하기 위해 도입한 방안이다.
    
    
  • Dense Index 와는 다르게 특정 키워드 데이터만 나열 및 주소값을 배정한다.
    
  • 주소값에 특정 데이터 범위에 대한 정보를 가지고 있기 때문에 특정 데이터를 조회 시
    해당 주소값이 가지고 있는 데이터 범위를 조회하고 이에 따른 필요 데이터가 있는 범주만 찾아서
    실제 데이터를 조회 할 수 있다.
    
    
  • 특정 범위 데이터만 인덱스정보로 가지고 있기 때문에 Dense Index 보다 적은 공간 사용을 사용하나
    데이터 기입, 삭제 시 위의 범주 정보도 바꿔야하는 과정도 거쳐야 하므로 Dense 인덱스 보다 
    데이터 변경 (기입, 삭제, 변경의 DML 작업) 속도가 느리다.
    
    

Primary 인덱스 에서는 데이터 조회시 아래의 과정을 거친다.

먼저, 루트페이지에는 실 데이터의 모든 정보가 아닌 조회를 위해 사용할 대표 데이터와 그 데이터가 실제 저장된 페이지 주소를 보관한다. (이에 따른 분류 저장 단위를 페이지라고 한다.)

그래서 데이터 조회시, 루트 페이지에 보관된 페이지 주소를 참조하여 그 페이지를 조회하면, 실제로 가리키는 데이터 공간을 (데이터 페이지) 를 조회하여 데이터를 조회한다.

이와 같이 중간 과정없이 데이터가 보관된 페이지를 직접적으로 조회하기 때문에 조회가 빠르다.

그러나 데이터 페이지 마다 보관 할 수 있는 데이터 개수는 제한되어 있기 때문에, 실제 데이터를 기입, 삭제, 수정등의 변경 작업 시 이에 따른 페이지를 분할하고, 데이터 재정렬 및 인덱스 정보도 갱신해야 하는 과정을 거친다. 데이터 변경작업 (DML) 에 Primary 인덱스가 불리한 이유다.

그래서 실무적으로 테이블 구성 및 데이터 기입시에는 테이블 생성 및 데이터 기입을 먼저 하고 인덱스를 후 생성 해 주는것이 좋다. (보통은 PK 후 추가가 다수다)

출처 : https://junghn.tistory.com/entry/DB-%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EC%99%80-%EB%84%8C%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EA%B0%9C%EB%85%90-%EC%B4%9D%EC%A0%95%EB%A6%AC

 

Secondary Index

 

각 데이터에 대해서 고유 값 (unique) 들이 있는 목록에 생성 할 수 있는 인덱스다. 개념적으로는 후보키에만 부여 할 수 있는 인덱스다. (후보키 : 고유 식별 번호, 주민번호 같이 각 데이터를 인식할 수 있는 최소한의 고유 식별 속성 집합이다.) 이 인덱스는 넌 클러스터 인덱스 (non-clustered index) 라고도 불린다. 

위의 Primary 에서 중간 단계가 도입된 인덱스이며, 이에 따라 첫단계에서 생성 및 구성되는 데이터-주소 배정 공간의 크기를 (mapping size) 줄일 수 있는 특징이 있다. 

아래 화면과 같이 Seconday Index 는 데이터를 조회시 주소 조회 -> 데이터 직접 접근이 아닌 
중분류 주소조회 -> 그 중분류 주소가 가지고 있는 데이터 주소값 확인 -> 데이터 주소값을 통하여 데이터 접근을 거친다.

 

Primary, 클러스터 인덱스와는 다르게 기존 데이터 자체를 재정렬하지 않는다. 

Primary, 클러스터 인덱스와 달리 여러개의 인덱스를 설정 할 수 있다. (단 최대 허용 개수는 RDBMS 마다 다르다.)

책의 색인 페이지같이 인덱스 및 이에 따른 데이터 정렬 보관 공간을 추가로 사용한다.
(실무적으로 테이블의 크기를 알아 볼 때, 자체 테이블 크기 및 이와 관련된 인덱스 공간등을 추가로 확인하는 이유다.)

 

아래 그림과 같이 넌 클러스터 인덱스는 클러스터 인덱스와 다르게 root, leaf, data node (page) 가 나뉘어져 있다.

데이터를 조회하는 세부 과정은 아래와 같다.

• 먼저 찾고자 하는 데이터를 찾을 시, root 에서 해당 데이터 키워드를 가지고 있는 leaf 페이지 주소를 탐색한다.
  
  
• 클러스터와는 다르게 leaf 노드에서 데이터를 바로 찾는게 아니라 해당 데이터를 가지고 있는 데이터 페이지의 주소값 및 그 페이지내의 데이터 위치값을 확인한다.
  
  
• 위의 참조한 주소 값을 통하여 실제 데이터를 조회한다.

• 클러스터와는 다르게 leaf 에서 주소를 한번더 탐색하므로 클러스터 보다 데이터 조회가 느리다.
  
  
• 그러나 해당 구조로 구성 시에는 데이터 변경에 따른 페이지 분할등의 작업이 필요 없으므로 (데이터 추가시 실데이터 페이지 구조 변경없이 leaf 페이지 정보만 변경 가능 하므로) 클러스터 인덱스 보다 데이터 변경작업시 유리한 이유가 이 때문이다.
  
  

출처 : https://junghn.tistory.com/entry/DB-%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4%EC%99%80-%EB%84%8C%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EA%B0%9C%EB%85%90-%EC%B4%9D%EC%A0%95%EB%A6%AC

 

위의 개념을 시작으로 각 RDBMS 는 각자 세분화된 인덱스 종류를 가지고 있으며 아래의 인덱스들은 모든 RDBMS 에서 범용적으로 사용하거나 응용하는 부차적인 인덱스다.

B-Tree Index

출처 : https://m.blog.naver.com/varkiry05/221347489960

Balanced Tree Index 의 약자이며, 다수의 RDBMS 에서 사용하고 있는 인덱스형태다.

데이터 조회시, Root - Branch - Leaf 를 거치나, 특정 상황에 따라 상호 연결된 Leaf 들을 거칠 수도 있다.

 

모든 단계의 페이지들은 참조 주소값을 가진다.

 

이 인덱스의 최대 장점은 어떤 데이터를 조회하든지, 이에 사용하는 조회 과정의 길이 및 비용이 균등 하다는데 있다.

단, 어떤 데이터를 조회 하든지 Root 에서 부터 Leaf 페이지를 모두 거처야 하기 때문에 데이터가 적은 테이블등의 단순 조회로 데이터를 조회하는 과정이 더 빠른 경우 대비 조회 속도가 느린 단점이 있다.

 

이 인덱스를 구성 시, 인지해야 할 내부 조건이 있다.

 

• 모든 노드 (페이지) 들은 2~4개의 데이터 값을 가진다. (단 이는 RDBMS 파라미터나 기타 설정 조건에 따라 바뀔 수 있다.)
  
  
• Root 에서 Leaf 로 도달하기 위해 거쳐야하는 탐색 거리는 동일하다.
  
  
• Root 를 제외한 Leaf 가 아닌 모든 노드들은 3~5 개의 하위 노드를 가진다.
• (예시는 보통 B tree 를 예시로 보여주기 위하여 자주 사용하는 3단계의 구성을 보인 것 이다. DB 구조에 따라 Root 와 Leaf 사이에 다단계의 노드가 구성 될 수도 있다.)
  
  
• Root, Leaf 를 제외한 모든 노드들은 n/2 (소수점 버림) 에서 n 개 사이의 하위 노드를 가진다. 여기서 n은 노드 구성 단계를 뜻한다. 예를 들어 위의 구조는 3단계의 구조를 가지므로 n은 3이며, 이 규칙을 따른다면 Branch 는 최소 1개에서 최대 3개의 하위 노드를 가진다.

Hash Index

(좋은 정보 참조 링크 : ju-hy.tistory.com/107)

Hash Index

 

주로 인메모리 DB (메모리가 디스크 스토리지의 메인 메모리에 설치되어 운영되는 DB 다. 알티베이스, Oracle Timestan, SAP Hana DB 등이 이 분류에 속한다.) 에서 사용하는 인덱스 종류다. 

 

출처 : https://blogs.oracle.com/timesten/what-is-the-best-timesten-index-for-my-oltp-application

해당 인덱스에서는 키값을 Hash 함수로 변환한 후, 이에 실제 데이터 주소와 연결하여 bucket 이라는 공간에 보관한다. 

 

타 인덱스 대비 equality (ex: where = '조건') 조회 속도가 매우 빠르다. 

 

그러나 위와는 반대로, 각 해쉬값에 주소값을 배정하는 인덱스의 특징에 따라 범위로 조회하는 작업은 느리다.

 

또한 범위로 묶어서 보관하는 인덱스가 아니므로 데이터 개수가 증가 함에 따라 범위로 묶어서 보관하는 인덱스보다 더 큰 저장공간을 필요로 한다.