[데이터베이스] 인덱스, B-Tree

1. 데이터를 저장하는 매체의 종류

CPU, 메모리와 같으 전기적 특성을 가지고 있는 장치의 성능은 빠른 속도로 발전했지만, 디스크와 기계식 장치의 성능은 제한적으로 발전했다.

그렇기 때문에 데이터베이스 성능 튜닝은 기계식 장치인 디스크의 I/O를 줄이는 것이 가장 중요한 포인트이다.

데이터를 저장할 수 있는 매체는 내장 디스크, DAS, NAS, SAN이 존재한다.

 - 내장 디스크 : PC내부 공간에 장착할 수 있는 갯수가 제하적이며, 용량이 부족한 경우 많이 존재

 - DAS : 내장 디스크의 용량의 문제를 해결, SATA, SAS와 같은 케이블로 하나의 PC에만 연결이 가능. 
           최대 200개 까지 연결하여 사용가능하지만 여러 PC 공유 불가

 - NAS : 케이블이 아닌, TCP/IP를 통해 연결이 되며, SATA, SAS보다는 상대적으로 느린 속도를 지원하지만, 여러 PC가 공유 가능

 - SAN : DAS로 구현 불가능한 대용량의 스토리지 공간 제공, 여러 PC와 공유가 가능하며, 광케이블로 연결되어 있기 때문에 SATA, SAS보다 빠름
               구축 비용이 많이 발생하기 때문에 중요한 데이터를 보관하는데만 사용

드라이브를 대체하기 위한 저장 매체 SSD가 등장하고 있다. 기존의 드라이브는 원판을 기계적으로 회전시켜 데이터를 읽고 썼지만, SSD는 원판을 

제거하고, 플래시 메모리를 통해 데이터를 읽고 쓰기를 한다. CPU, DRAM보다는 느리지만, 디스크보다는 빠른 속도를 지원한다.

순차 I/O에서는 디스크와 SSD의 속도 비교를 할 때 큰 차이를 느낄 수 없지만, 랜덤 I/O에서는 굉장히 큰 차이를 경험할 수 있다.

2. 랜덤 I/O, 순차 I/O

I/O는 디스크의 원판을 회전시켜 원하는 데이터가 저장된 위치로 디스크의 헤더를 이동시키는 것을 의미한다. 예를들어, 3개의 데이터를 읽는다고 할 때, 

순차 I/O는 한번에 3개의 데이터를 연속적으로 읽기 때문에(디스크의 헤더를 순차적으로 이동하여) 한번의 요청으로 처리가 가능하다. 

그러나 랜덤 I/O는 디스크의 헤더를 비연속적으로 이동시켜야 하기 때문에 세번의 요청으로 처리가 가능하다.

데이터베이스 튜닝은 디스크 헤더의 이동을 최소화하여 많은 데이터를 접근하게 설계하는 것이다. 그렇다면 그 방법은 무엇이 있을까?! 인덱스다!

3. 인덱스

인덱스는 책의 가장 마지막 페이지인 "찾아보기, 색인"으로 비유가 되고 있다. 그 이유는 인덱스의 구조와 정렬, 두 가지의 이유이다.

먼저 "찾아보기"는 데이터와 페이지 번호가 쌍으로 이루어져 있고, 인덱스 또한 Key(찾으려는 데이터), Value(찾으려는 데이터의 주소)가 쌍으로 이루어져 있다.

그리고 "찾아보기", 인덱스 모두 빠른 탐색을 지원하기 위해 정렬이 되어 있다. 데이터베이스의 인덱스는 Key는 SortedArray 자료구조를 사용해서 항상 정렬된

상태를 유지하고, Value는 ArrayList 자료구조를 사용해서 정렬이 아닌, 순차적으로 데이터를 저장하게 되어 있다.

SortedArray를 사용해서 정렬된 Key 값을 가지고 있으면 탐색 측면에서는 빠른 속도를 지원할 수 있지만, 삽입, 삭제, 수정을 할 때는 항상 정렬을 해야하기 

때문에 느린 속도를 지원한다. 결국은 인덱스를 사용하면 삽입의 성능은 떨어질 수 있지만 검색의 효율을 높일 수 있다. 그렇다면 인덱스로 모두 만들면 될까?

SELECT 쿼리문에서 WHERE 조건문에 자주 쓰이는 칼럼을 인덱스로 구성하면 빠른 검색을 할 수 있겠지만, 오히려 너무 많다면 인덱스의 크기가 비대해져

성능이 저하될 수 있다. 참고로 기본키는 자동으로 인덱스를 생성한다. 아마 기본키는 WHERE 조건문에 가장 많이 사용되서 이지 않을까?

4. B-Tree 인덱스 (Balanced Tree Index) : Binary Tree가 아니다!

B-Tree 는 칼럼의 원래 값을 변경하지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지하고 있다. 뒤에서 다룰 예정이지만, Hash 인덱스는 칼럼의 값을 Hash 값을 계산해서 인덱싱하는 알고리즘이다. 값을 변형한다는 것이다. 그러나 B-Tree 그렇지 않다는 것이 가장 큰 차이이다.

B-Tree 인덱스는 루트노드, 브랜치 노드, 리프 노드로 구성이 되있으며, 리프노드의 값에는 실제 데이터 파일의 주소가 담겨져 있다. 그림에서 보다시피

인덱스의 키들은 모두 정렬되있지만, 값들은 정렬되어있지 않다. 그렇기 때문에 데이터가 추가되면 데이터의 값을 정렬하지 않고, 비어있는 공간에 순차적으로

삽입되도록 되어 있다.

5. B-Tree 인덱스 키 추가 / 삭제 / 변경 / 검색

테이블에 데이터를 삽입하는 비용이 1이라고 한다면, 인덱스 하나를 추가하는 비용은 1 ~ 1.5 라고 한다. 그 이유는 인덱스는 항상 정렬된 상태를 유지해야

하기 때문에 인덱스의 적절한 위치를 찾는데 많은 비용이 소모되기 때문이다. 그리고 만약 실제 데이터를 가지고 있는 리프노드가 가득찬다면, 리프노드를

분리해야하는데 이때는 브랜치 노드, 루트 노드에도 영향을 미칠 수 있다. 그렇기 때문에 인덱스를 추가하는 것이 비용이 많이 든다는 것이다!

인덱스를 추가하는 과정에서, 인덱스 추가가 완료될 때까지 쿼리문을 동작하지 않는 방식과 인덱스 추가를 지연처리할 수 있는 방식 두가지가 존재한다.

인덱스를 삭제할 때는 디스크의 헤더의 위치를 삭제하려는 인덱스로 이동시키고, 삭제 마크를 남기면 삭제가 된다. 마킹된 인덱스의 공간은 재사용 가능하다.

인덱스 키 값에는 저장될 리프노드의 주소를 담고 있기 때문에 인덱스의 키값만 변경하는 것은 불가능하다. 그렇기 때문에 인덱스의 키 값을 변경할 때는

인덱스를 삭제하고, 삽입하는 과정을 거처야만 한다.

인덱스 키를 검색했을 때는 인덱스 값의 100% 일치 또는 앞자리 일치만으로 검색 가능하다. 대소비교, 뒷자리 일치로는 검색이 불가능하다.