인덱스에 대한 설명과 구조

[GIVEN53]

자료구조, 스캔 방식, 장단점 등

[le2sky]

[개념, 특징, 장단점]
인덱스는 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조로 백과사전의 색인과 같습니다.
저장되는 컬럼의 값을 사용하여 항상 정렬된 상태를 유지하는 것이 특징입니다.
이러한 특징으로 인해 인덱스는 INSERT, UPDATE, DELETE의 성능이 희생된다는 것이 단점입니다.

[자료구조]
MySQL InnoDB를 기준으로 설명드리자면, B+Tree와 같은 변형 B-Tree 자료구조를 이용해서 인덱스를 구현합니다.
기본 토대는 B-Tree 인덱스이기 때문에 이를 기준으로 설명합니다.
B-Tree 인덱스는 컬럼의 값을 변형하지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지합니다.

B-Tree(Balanced-Tree)에서는 크게 3가지 노드가 존재합니다.
최상위에 하나의 루트 노드가 존재하며, 가장 하위 노드인 리프 노드가 존재합니다.
이 두 노드의 중간에 존재하는 브랜치 노드가 존재합니다.
최하위 노드인 리프 노드에는 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있습니다.

InnoDB 스토리지 엔진에서는 세컨더리 인덱스(프라이머리 인덱스를 제외한 모든 인덱스)의 리프 노드에는 레코드의 PK가 저장됩니다. 따라서 세컨더리 인덱스 검색에서는 레코드를 읽기 위해 PK를 가지고 있는 B-Tree를 다시 한번 검색해야합니다.
이러한 특징 때문에 모든 세컨더리 인덱스는 PK를 가지고 있습니다. 따라서 인덱스로만 처리될 수 있는 경우가 많은데, 이를 커버링 인덱스라고 합니다.

[스캔 방식]

MySQL에는 크게 인덱스 레인지 스캔, 인덱스 풀 스캔, 루스 인덱스 스캔 방식이 있습니다.

인덱스 레인지 스캔은 검색할 인덱스 범위가 결정되었을 경우 사용하며 가장 빠릅니다.

• 인덱스에서 조건을 만족하는 값이 저장된 시작 리프 노드를 찾습니다.(index seek)
• 시작 리프 노드부터 필요한 만큼 인덱스를 차례대로 읽습니다. (index scan)
• 인덱스 키와 레코드 주소를 이용해 저장된 페이지를 가져오고 레코드를 읽어옵니다.

레코드를 읽어오는 과정에서 랜덤 IO가 발생할 수 있습니다.
읽어야할 데이터 레코드가 전체 20-25%의 경우에는 풀 테이블 스캔(순차 IO를 이용)이 더욱 좋을 수 있습니다.

인덱스 풀 스캔은 인덱스를 사용하지만 인덱스를 처음부터 끝까지 모두 읽는 방식입니다.

• 인덱스를 ABC 순서로 만들었는데 조건절에 B 혹은 C로 검색하는 경우 사용됩니다.
• 인덱스를 생성하는 목적은 아니지만, 그래도 풀 테이블 스캔보다는 낫습니다. (데이터 레코드까지 읽지 않는 경우)

루스 인덱스 스캔은 듬성듬성하게 인덱스를 읽는 것을 의미합니다. (앞서 언급한 인덱스 레인지, 인덱스 풀 스캔은 타이트 인덱스 스캔으로 분류됩니다. )

• 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리합니다.
• group by, max(), min() 함수에 대해 최적화하는 경우에 사용됩니다.

[J-I-H-O]

<개요>

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용해 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조 입니다.
책의 색인과 같이 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 합니다.
인덱스는 특정 열이나 열의 조합에 대해 생성할 수 있습니다.

인덱스를 사용하지 않은 컬럼을 조회해야 하는 상황이라면, 전체를 탐색하는 full scan을 수행해야 합니다. full scan은 전체를 비교하기 때문에 처리 속도가 떨어집니다.

<장단점>

• 장점
  • 인덱스를 적용하면 테이블을 조회하는 속도와, 그에 따른 성능을 향상시킬 수 있습니다.
    • WHERE, JOIN, ORDER BY 절 등
      • 인덱스는 미리 데이터를 정렬해 관리하기 때문에, ORDER BY에 의한 정렬 과정을 생략할 수 있음
      • 최소값과 최대값을 쉽게 가져올 수 있다는 부수적인 장점 존재
  • 전반적인 시스템의 부하를 줄일 수 있습니다.
• 단점
  • 인덱스를 관리하기 위해 DB 의 약 10%에 해당하는 저장공간이 필요합니다.
  • 인덱스를 관리하기 위한 추가 작업이 필요해 쓰기 성능이 저하될 수 있습니다.
    • DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있습니다. 따라서 인덱스가 적용된 컬럼에 삽입, 삭제, 갱신이 수행될 때마다 인덱스도 함께 갱신되어야 하기 때문에 오버헤드가 발생합니다.
      • INSERT : 새로운 데이터에 대한 index 추가
      • DELETE : 삭제하는 데이터의 인덱스를 사용하지 않음 처리 (삭제 하지는 않음)
      • UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대한 인덱스를 추가
  • 인덱스를 잘못 사용할 경우, 오히려 성능이 저하될 수 있습니다.
    • 만약 INSERT, DELETE, UPDATE 가 빈번한 컬럼에 인덱스를 걸게되면 인덱스의 크기가 비대해져 오히려 성능이 저하될 수 있습니다. (인덱스를 사용하지 않음 처리할 뿐, 삭제하지 않기 때문)

<인덱스를 사용하면 좋은 경우>

• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• WHERE, JOIN, ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼 (= 데이터의 카디널리티가 높은 컬럼)
  • 가령 남자와 여자라는 도메인만 있는 성별 컬럼에 인덱스를 거는 경우, 탐색할 수 있는 값이 2개 밖에 없으므로 검색할 값이 중복되고 그만큼 검색할 대상이 증가함
  • 다중 컬럼을 인덱싱할 때에는 카디널리티가 높은 컬럼에서 낮은 컬럼 순으로 인덱싱
• 테이블의 전체 데이터 중 10 ~ 15% 이하의 데이터를 처리하는 경우

<자료구조>

인덱스를 구현하기 위해서 대표적으로 해시 테이블과 B+Tree를 사용합니다.

• 해시 테이블(Hash Table)
  • key-value 쌍으로 데이터를 저장하는 구조
  • (컬럼의 값, 데이터의 위치) 를 key-value로 사용
    • 컬럼의 값을 해시 함수를 사용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 값을 찾아 검색
  • 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성으로 인해 부등호 연산과 같이 범위 검색이 자주 사용되는 경우에는 적합하지 않음
• B+Tree

• 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조.
  binary tree와 개념적으로 비슷하며, key 값으로 정렬되어 있음
  • Root node : 검색 경로의 출발점
  • Leaf node : 인덱스(key)와 함께 실제 검색할 데이터(value)가 저장된 노드
  • Non-leaf node : Leaf node까지 가기 위해 다음 경로 노드의 key 값(데이터를 위한 인덱스)을 가지고 있는 노드
  • LinkedList : 부등호를 이용한 순차 검색 연산이 용이하도록 Leaf node 들을 LinkedList로 연결
• SELECT 쿼리를 날리면 Root node에서 시작하여 Non-leaf nodes를 거쳐 Leaf node 검색
  • 각 노드에 저장된 key값을 순차적으로 비교하며, 현재 보고있는 key가 찾으려는 key보다 작다면 왼쪽 Child Pointer를, 크다면 오른쪽 Child Pointer를 통해 자식 노드로 찾아감

https://aeliketodo.tistory.com/144
https://mangkyu.tistory.com/96
https://choicode.tistory.com/27
https://velog.io/@kyeun95/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-B-Tree%EB%9E%80
https://adjh54.tistory.com/163