DB 인덱스 개요 및 자료구조 ( B-Tree, B+Tree )

DB Index
。데이터베이스에서 검색 속도를 향상시키기 위한 책갈피 역할의 정렬된 자료구조
▶ DB Table에 저장된 데이터의 컬럼을 인덱스로 설정 및 정렬하여 데이터를 빠르고 효율적으로 검색

。인덱스를 설정 시 향후 SQL Query를 실행하는 경우 Optimizer에 의해 쿼리 플랜에 자동으로 인덱스로서 반영 및 결정되어 결정된 쿼리 플랜에 따라 최소한의 비용과 최적의 성능으로 SQL Query를 처리

。WRITE 성능을 포기하고 READ 성능을 극대화하므로 수정보다는 검색에 주로 사용되는 컬럼에 인덱스를 설정
▶ DB의 경우 WRITE에 비해 READ가 압도적으로 많으므로 WRITE 성능을 일부 포기 ( 약 2 : 98 비율 )

。기본적으로 클러스터형 인덱스, 비클러스터형 인덱스는 B+Tree Index
▶ 인덱스는 검색 성능을 높이기위해 B+Tree 자료구조를 사용

• 인덱스 설정 시 가장 카디널리티가 많은 컬럼을 인덱스 컬럼으로 설정하는게 좋다.
  。카디널리티가 높을 수록 행 중복이 적으므로 정렬을 더 많이 수행하여 효율이 더 좋음
  
  。주로 복합인덱스에서 가장 카디널리티가 많은 컬럼을 좌측으로 설정하는 이유

인덱스 생성 방법

• 클러스터형 인덱스 생성
  
  。PK를 설정 시 자동으로 생성
  ▶ 테이블 당 하나만 생성가능
  
  。해당 인덱스는 B+ Tree 자료구조로서 PK를 기준으로 오름차순 정렬
  
  
• 비클러스터형 인덱스 생성

CREATE INDEX 인덱스명
ON 테이블명(인덱스적용컬럼명);

ALTER TABLE 테이블명
ADD INDEX 인덱스명 (인덱스적용컬럼명);

。CREATE INDEX 구문으로 생성
▶ 여러 비클러스터형 인덱스를 생성가능

。해당 인덱스는 B+ Tree 자료구조로서 컬럼을 기준으로 오름차순 정렬
▶ 복합 인덱스의 경우 컬럼을 좌측으로 설정하면서 컬럼 순서대로 오름차순 정렬

。이미 데이터 테이블에서는 PK로서 클러스터형 인덱스를 기준으로 오름차순 정렬되어 인덱스 테이블 상에서 오름차순 정렬됨을 인지

• 특정 인덱스 컬럼 기준으로 ORDER BY DESC가 적용된 SQL Query경우

CREATE INDEX 인덱스명
ON 테이블명(인덱스적용컬럼명 DESC);

。해당 인덱스는 B+ Tree 자료구조로서 컬럼을 기준으로 내림차순 정렬되도록 설정
▶ 내림차순 데이터 조회속도 개선

。다음 SQL Query에서 WHERE 문에서 order_date 컬럼에 대해 조건이 설정 및 해당 컬럼이 ORDER BY 절에서 DESC로 출력되도록 적용
▶ 인덱스를 DESC로 설정하여 인덱스 튜닝

    select *
    from
        ch3_orders o1_0
    where
        o1_0.order_date>='2023-01-01T00:00'
    order by
        o1_0.order_date desc

ALTER TABLE ch3_orders 
ADD INDEX orderdate_idx_to_ch3orders (order_date desc); 

인덱스 네이밍 컨벤션
。인덱스 : 컬럼명_idx_to_테이블명

。복합인덱스 : 컬럼명1_and_컬럼명2_idx_to_테이블명

ex ) CREATE INDEX is_adult_and_category_idx_to_book ON book(name);

DB에서 데이터 조회 시 두가지 방식

• FULL SCAN : 테이블 전체 조회
• INDEX SCAN : 테이블 내 필요한 인덱스만 조회

인덱스 사용의 장 / 단점


장점 :

• 인덱스 컬럼에 따라 데이터가 정렬되어 인덱스 위치를 바로 참조하여 빠른 조회가 가능.
  。 자주 사용하는 컬럼에 인덱스 지정 시 테이블 전체를 검색하는 Full Scan을 하지않고 컬럼의 인덱스 위치로 바로 점프 및 탐색하여 데이터 조회 속도 향상
  ex ) WHERE name = "이정수"에서 CREATE INDEX 인덱스 ON 테이블(name) 지정 시 해당 name 기준으로 정렬하여 조회속도 향상
  
  。WHERE, JOIN, ORDER BY, GROUP BY 등의 연산이 주로 적용되는 컬럼에 선언하여 정렬하여 쿼리 실행 시간 감소
  ▶ 인덱스에 의해 이미 정렬되어 있으므로, ORDER BY와 GROUP BY 적용 시 비용 감소


단점 :
  
  
• 인덱스를 컬럼에 지정 시 B+Tree 자료구조로 인해 디스크와 buffer pool 공간을 사용
  。인덱스는 Buffer Pool에 등록되어 인덱스가 많을수록 자주 쓰는 인덱스가 Cache Hit될 확률이 적어져서 캐시 효율 저하
  
  
• 크기가 작은 테이블에서 WHERE 검색하는 경우 인덱스보다 FULL SCAN이 더 빠를 수 있다.
  。단, 인덱스가 존재하더라도 Optimizer의 판단에 따라 FULL SCAN이 수행될 수 있다.
  
  
• 자주 변경되는 컬럼에 인덱스 적용 시 INSERT / UPDATE / DELETE 등의 WRITE 성능 저하
  。잦은 데이터 삽입 / 삭제 시 인덱스 자료구조 재정렬로 인한 성능저하 발생 가능성 존재

인덱스 자료구조
。인덱스는 검색 성능을 높이기위해 자료구조로 B+Tree를 사용
▶ 이진검색트리와 유사하지만 다중키를 통해 N+1 개의 자식노드를 가질 수 있어 이진검색트리 대비 높이가 낮아 거쳐갈 노드가 적어 검색속도가 빠르다.

• 이진검색트리와 동일한 정렬트리
  。특정 노드 N을 기준으로 좌측서브트리의 노드 KeyValue는 항상 노드 N보다 작고, 우측서브트리의 노드 KeyValue는 항상 노드 N보디 큰 특징을 가짐.
  ▶ 중위순회를 수행하는 경우 오름차순 정렬
  
  
• 인덱스 자료구조로 해시테이블을 사용하지 않는 이유?
  。B-Tree, B+Tree는 다른 자료구조에 비해 범위검색에 특화됨
  ▶ 해시테이블을 사용 시 해시값을 통해 $O(1)$의 속도로 빠르게 데이터를 조회할 수 있으나 범위검색에 적합하지 않음.

B-Tree( Balance Tree )


。이진검색트리를 개선한 균형트리 구조로서 모든 노드에 키 값과 데이터 포인터를 저장하는 자료구조
▶ 데이터 포인터는 실제 데이터가 저장된 위치를 저장

。 검색 / 삽입 / 삭제 속도 : $O(log N)$
▶ 이진검색트리와 유사하게 대소비교를 통해 범위를 줄여서 검색을 수행하므로 시간복잡도 : $log(N)$

。데이터 검색 시 Full Scan이 아닌 B-Tree Index를 통해 탐색범위를 줄이면서 빠르게 검색이 가능

• 이진검색트리 대비 B-Tree 개선점
  
  。다중 키 : 각 노드는 여러 Key를 저장 및 오름차순으로 정렬
  
  ▶ 다중키를 통해 이진검색트리 대비 낮은 트리 높이를 가지므로 탐색 시 거쳐갈 노드 수가 감소하여 검색속도가 빠르다
  ▶ 다중키를 통해 N개의 Key에 대해 총 N+1개의 자식노드를 가질 수 있다.
  
  。효율적인 범위 검색 : 키들이 정렬되어 범위 검색이 용이
  ▶ 이는 B+ Tree에서 더욱 개선
  
  。디스크 I/O 감소 : 한 노드에 많은 키를 저장하므로 디스크 접근 횟수 감소
  ▶ 디스크 I/O 연산은 CPU 연산에 비해 수천배 느리므로 페이지폴트 사례처럼 최소화하는게 좋다.
  
  
• 노드의 키 갯수 : N일때 최대 N+1개의 자식노드를 가질 수 있다.
  
  ▶ 노드의 키 갯수 = 1인 경우 자식노드는 총 2개를 가질 수 있다.
  
  ▶ 노드의 키 갯수 = 2인 경우 자식노드는 총 3개를 가질 수 있다.
  
  
• B-Tree 저장 원리
  。부모노드의 55, 65라는 2개의 키값이 존재하는 경우 자식노드는 총 3가지 케이스로 구분해서 키값을 저장
  
  좌측 자식노드 : 55보다 작은 값
  중앙 자식노드 : 55~65의 값
  우측 자식노드 : 65를 초과하는 값
  
  
• 모든 리프노드는 동일 레벨에 존재
  

  B-Tree의 단점
  。데이터가 리프 - 중간 - 루트 노드로 광범위하게 흩어져서 효율 감소
  
  。리프 노드 간 연결이 없어 구간범위 데이터 검색 시 비효율적
  ex ) 40 ~ 60까지의 데이터 조회 시 리프노드끼리 연결이 안되있어서 루트노드를 경유해서 일일이 조회해야함.
  
  ▶ 다음 단점으로 인해 B+Tree를 사용

B+Tree

。B-Tree를 개선하여 리프노드가 Edge를 통해 연결 리스트 로서 연결되며 리프노드에만 키 값과 데이터 모두 저장하는 자료구조
▶ B-Tree에 비해 범위 검색 성능이 더 좋음
▶ 루트노드, 중간노드는 키 값만 저장하여 포인터 역할만 수행

。대부분의 RDBMS의 인덱스에서 사용하는 방식
▶ 대표적으로 InnoDB( = MySQL의 Storage 엔진) 이 존재

• 리프노드 간 연결리스트를 통한 연결성이 추가되어 범위 검색 향상
  
  。45 ~ 55까지의 데이터 범위 조회 시에도 루트 노드를 경유할 필요없이 연결리스트를 통해 조회
  
  
• 그래프 내 전체 노드가 아닌 B+Tree의 리프노드에만 데이터를 저장하여 메모리 효율 향상
  。 데이터들이 균일하게 리프노드에 몰려있어 물리적으로 동일한 디스크 블록내 저장가능
  
  
• B-Tree에 비해 B+Tree의 단점
  。리프 노드 간의 연결에 대한 데이터도 추가적으로 관리
  ▶ 데이터의 생성, 수정, 삭제 시 B-Tree보다 더 많은 오버헤드가 발생