인덱스(Index)와 힌트(Hint)

인덱스(Index)

• 인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
•  특정 컬럼에 인덱스를 생성하면 해당 컬럼에 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.
• 쿼리문에  인덱스가 생성된 컬럼을 WHERE 조건으로 걸어주면 옵티마이저가 판단하여 생성된 인덱스를 탈 수 있다.
  • 옵티마이저 : 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성해주는 DBMS의 핵심 엔진이다.
• 목차와 같은 역할을 한다.

---

인덱스(Index)의 구조

• 자료 구조에는 배열, 리스트, 스택, 큐, 해시, 트리 등 수많은 종류가 존재한다. 그 중에서도 인덱스에서 가장 많이 쓰이는 구조는 트리구조이며, 그 중에서도 'B Tree' 를 주로 사용한다.
• B Tree는 이진트리에서 발전하여 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 균형이진트리의 확장판이다.
• B Tree 의 종류는 3가지로, 다음과 같다.
  1. B-Tree
  2. B+Tree
  3. B*Tree
• 이 외에도 인덱스는 여러 분류방식으로 분류할 수 있는데, 그 내용은 다음과 같다.
  • 역할별
    1. 클러스터 인덱스
       • 테이블에 기본키(PK)에 대해 적용되는 인덱스
       • 데이터가 테이블에 물리적으로 저장되는 순서를 설정한다.
       • 데이터가 삽입되는 순서에 상관없이 인덱스로 생성되어 있는 컬럼을 기준으로 정렬하여 삽입한다.
       • 테이블 당 하나의 인덱스만 생성할 수 있다. 
       • 데이터의 입력/수정/삭제 시에도 정렬을 수행하여 입력/수정/삭제 속도는 더 느리다
    2. 비클러스터 인덱스 : 테이블에 기본키 외에 다른 컬럼에 적용되는 인덱스
       • 테이블에 저장 된 물리적인 순서에 따라 데이터를 정렬하지 않으므로 정렬이 되어있지 않다.
       • 데이터가 저장되는 별도의 공간이 필요하다.
    3. 유니크 인덱스 : 테이블에 기본키는 아니지만, 중복을 허용하지 않는 유니크 속성이 들어간 컬럼에 적용되는 인덱스
  • 데이터 저장 방식 별
    1. B-Tree 인덱스
    2. R-Tree 인덱스
    3. Hash 인덱스
    4. Fractal-Tree 인덱스
    5. Merge 인덱스
  • 데이터 중복 허용 여부 별
    1. 유니크 인덱스
    2. 논 유니크 인덱스
  • 기능 별
    1. 전문 검색용 인덱스
    2. 공간 검색용 인덱스

---

이러한 트리 구조들 중에서도 B Tree 인덱스에 대해 자세히 알아보려고 한다.

먼저, B Tree의 기초라고 할 수 있는 이진트리에 대해 간단히 알아보자.

[이진트리]

• 이진트리는 각각의 노드가 최대 두 개의 자식노드를 가지는 트리 자료구조를 말한다.

이진트리

• 이진트리에는 여러 종류가 있는데, 그 중에서도 B Tree는 '균형이진트리' 의 일종이다.
• 이진트리의 종류는 다음과 같다. 
  1. 정이진트리(Full Binary Tree) = 포화이진트리 : leaf node가 끝까지 꽉 찬 트리를 의미한다.
  2. 완전이진트리(Complete Binary Tree) :  마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 찬 트리를 의미한다.
  3. 균형이진트리(Balanced Binary Tree) : 리프 노드들의 레벨 차이가 최대 1까지만 나는 트리를 의미한다. 2 이상의 차이가 나게 되면 균형이 깨지며, 별도의 로직을 통해 다시 균형을 유지하게 된다.

이진트리의 종류

---

[B-Tree]

• 이진트리와는 다르게 하나의 노드에 많은 정보를 담을 수 있다.
• 노드 하나에 여러 데이터가 들어갈 수 있다.
• 정렬된 데이터가 들어있다.
• 모든 자료는 중복되지 않는다.
• 자식 노드의 개수는 n+1 개이다.
• 각 노드에는 여러개의 Key가 있고 각 Key에 대응하는 데이터도 갖고있다.
• 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
• 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
• 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
• 각 key 들의 왼쪽 자식들은 항상 key 보다 작은 값을, 오른쪽은 큰 값을 가진다.
• 값을 검색하는 과정은 다음과 같다.
  • https://rebro.kr/169 참조

---

[B+Tree]

• 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 조회할때에는 트리의 모든 노드를 방문해야 한다는 단점을 가지고 있는 B-Tree의 단점을 해소하기 위한 것으로, B-Tree의 확장 개념이다.
• Leaf Node만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드(Inner Node)들은 데이터를 위한 인덱스(Key)만을 갖는다.
  • 노드는 가장 상단에서 기준이 되는 루트(Root) 노드와 중간 단계인 브런치(Branch)노드, 가장 마지막 단계인 리프(Leaf) 노드로 구성되어 있다.
• 리프 노드들은 LinkedList로 연결되어 있다.
• leaf node가 아닌 자료는 인덱스 노드라고 부르고, leaf node 자료는 데이터 노드라고 부른다.
• 인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재한다.
• 데이터 노드의 Value값에 데이터가 존재한다.
  • 리프 노드외에는 데이터 노드를 저장하지 않기 때문에 메모리의 확보가 가능하며, 이로인해 하나의 노드에 더 많은 포인터를 갖게 되므로 결과적으로 트리의 높이가 낮아져 검색 속도를 향상시킬 수 있다.
• 키값은 중복될 수 있다. 하지만 데이터는 중복될 수 없다.
• 데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다는 특징을 가지고 있다.
• 리프노드가 아닌 노드의 키값의 수는 그 노드의 서브 트리 수보다 하나가 적다.

---

[B-Tree]와 [B+Tree] 비교분석표

구분	B-Tree	B+Tree
데이터 저장	리프 노드. 브랜치 노드 모두 가능	리프 노드에만 저장 가능
트리의 높이	높음	낮음 (한 노드 당 key를 여러개 담을 수 있음)
풀 스캔시에 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색 (각 노드가 연결리스트로 연결되어 있음)
키 중복	없음	있음 (리프 노드에 모든 데이터가 있음)
검색	자주 접근하는 노드를 루트 노드 가까이 배치할 수 있고 루트 노드에 가까울 경우 브랜치 노드에도 데이터가 존재하기에 속도가 빠름	무조건 리프 노드까지 도달해야하므로 비교적 속도가 느림
linked list(연결 리스트)	없음	리프 노드끼리 연결되어 있음

---

---

[B*Tree]

• 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성된다는 단점이 있는 B-Tree를 보완하기 위해 나왔다.
• 노드의 추가적인 생성과 추가적인 연산의 최소화를 위해서 B-Tree에서 몇 가지 규칙이 추가되었다.
• 루트 노드는 자신이 리프 노드가 되지 않는 이상 적어도 2개 이상의 자식 노드를 가진다.
• 루트 노드가 아닌 노드들은 적어도 2[(M-2)/3]+1개의 자식 노드를 가지고 있습니다. (최대 M개)
• 기존 노드의 자식 노드 수 최소 제약조건이 2M/3개로 늘어났다.
• 노드가 가득 차면 분열 대신 이웃한 형제 노드로 재배치한다.

---

[해시 테이블(Hash Table)]

• (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다.
• Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
• (key, value) = (컬럼의 값, 데이터의 위치) 로 구현한다.
• 실제로 인덱스에서 잘 사용되지 않으며 그 이유는 해시 테이블이 등호(=) 연산에 최적화되어있기 때문이다.
  • DB에서는 부등호(<, >) 연산이 자주 사용되는데, 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하기에 적합하지 않다.

---

인덱스(Index)의 장단점

[장점]

 

1. WHERE절의 효율적인 사용
   • 테이블을 만들고, 데이터가 쌓이면 내부적으로 정해진 순서 없이 데이터가 저장이 된다.
     • 이러한 상황에서 WHERE 절을 사용하게 되면 특정 조건에 맞는 데이터를 찾기 위해 모든 행의 데이터를 전부 다 읽어서 검색 조건과 맞는지 비교해야 한다. (이것을 풀 스캔이라고 한다.)
     • 하지만 인덱스를 설정한 컬럼을 조회하게 되면 데이터가 정렬되어 있기 때문에 해당 조건에 맞는 데이터를 빠르게 찾아낼 수 있다.
2. ORDER BY 절의 미사용
   • ORDER BY 는 부하가 많이 걸리는 작업이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지며 메모리보다 큰 작업이 필요하다면 디스크 I/O에서도 추가적으로 작업이 이루어지기 때문이다.
   • 인덱스를 사용하면 이러한 ORDER BY 절에 의한 정렬을 피할 수 있다.
3. MIN, MAX의 효율적인 처리
   • 데이터가 정렬되어 있기에 풀 스캔 없이 빠른 작업이 가능하다.
4. 전반적인 시스템의 부하를 줄일 수 있다.
5. 키 값을 기초로 하여 테이블에서 검색과 정렬 속도를 향상시킨다.

---

[단점]

1. DML에 취약하다.
   • INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다. 
     • 그래서 검색을 위주로 하는 테이블에 생성하는 것이 좋다.
2. 소규모 데이터에는 적합하지 않다.
   • 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이다.
   • 100만개의 데이터가 있는 테이블이라면 인덱스를 사용하는 것이 맞지만, 10개의 데이터만 있는 테이블이라면 풀스캔을 사용하는 것이 더 빠를 수 있다.
3. 인덱스가 많은 것은 좋지 않다.
   • 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다.
   • 인덱스를 사용하게 되면 쿼리문 하나의 속도는 빨라지지만, 많이 쌓이게 되면 전체적인 데이터베이스의 성능 부하를 일으킨다.
   • 인덱스를 생성하는 것보다는 SQL문을 좀 더 효율적으로 짜는 것이 더욱 좋다
   • 인덱스를 생성하는 것은 최후의 수단이다.

---

[인덱스 생성 시 주의할점]

1. 조건절에 자주 등장하는 컬럼으로 사용한다.
2. PK로 인덱스를 거는 것이 가장 좋다.
3. 중복되는 데이터가 최소한인 컬럼으로 사용한다.
4. ORDER BY나 JOIN 조건 등으로 자주 사용되는 컬럼으로 사용한다.

---

HINT

• SQL 튜닝의 핵심적인 부분으로 일종의 지시 구문을 말한다.
• 옵티마이저의 실행 계획을 원하는대로 바꿀 수 있게 해준다.
  • 옵티마이저가 항상 최선의 계획을 수립할 수 없기 때문에 잘못된 실행 계획을 개발자가 직접 바꿀 수 있게 해준다.
• 사용자가 특정 SQL 문장에서 어떤 인덱스가 선택도가 높은지 알고 있는 경우 옵티마이저에 의존한 실행 계획보다 훨씬 효율적인 실행 계획을 구사할 수 있다.
• 액세스 경로, 조인 순서, 병렬 및 직렬 처리, Optimizer의 목표(Goal) 변경이 가능하다.
• 모든 Hint의 기본 사용법은 쿼리 서두에 힌트를 명시하는 것이다.
• HINT는 크게 두 가지로 구분할 수 있다.
  1. 옵티마이저 힌트(Optimizer Hint)
  2. 인덱스 힌트(Index Hint)

---

[옵티마이저 힌트(Optimizer Hint)]

• 옵티마이저를 제어하는 방법 중 하나는 optimizer_switch 시스템 변수를 설정하는 것인데 이는 뒤에 모든 쿼리 실행에 영향을 주기 때문에 권장하지 않는다.
• 그래서 제어를 원하는 부분을 지정할 수 있는 옵티마이저 힌트를 사용한다.
• 명령문 내에 옵티마이저 힌트는 optimizer_switch 보다 우선시되어 적용된다.
• 옵티마이저 힌트는 다양한 영역에서 적용된다.
  • 전역 : 전체 쿼리에 영향을 준다.
  • 쿼리 블록 : 명령문 내에 특정 쿼리 블록에만 영향을 준다.
  • 테이블 : 쿼리 블록 내에 특정한 테이블에만 영향을 준다.
  • 인덱스 : 테이블 내에 특정 인덱스에만 영향을 준다.
• /*+ */ 주석 내에 지정해야 한다.
  • [ + ] 가 없으면 단순 주석이 되므로 반드시 붙여줘야 한다.

---

[인덱스 힌트(Index Hint)]

• 복잡한 쿼리의 경우 서로의 인덱스가 물리고 물려서 맞지 않는 인덱스를 사용하는 경우가 있는데, 이럴 경우에 사용한다.
• 강제적으로 할당한 Index를 이용하여 쿼리를 실행한다.
• JPA(hibernate)에서 사용이 불가능하기 때문에 JdbcTemplate 등을 이용하여 Native Query로 활용해야 한다.
• 사용방법은 다음과 같다.
  1. USE : 특정 인덱스를 사용하도록 권장한다.
  2. IGNORE : 특정 인덱스를 사용하지 않도록 지정한다.
  3. FORCE : USE와 동일한 기능이지만 보다 강하게 인덱스를 사용하도록 권장한다.
  4. USE INDEX FOR JOIN : 테이블간에 조인 뿐만 아니라 레코드를 검색하는 용도까지 포함한다.
  5. USE INDEX FOR ORDER BY : 명시된 인덱스를 ORDER BY 용도로만 사용하도록 제한한다.
  6. USE INDEX FOR GROUP BY : 명시된 인덱스를 GROUP BY 용도로만 사용하도록 제한한다.

TABLE_NAME [[AS] ALIAS] INDEX_HINT INDEX_LIST

INDEX_LIST:
    USE {INDEX|KEY}
      [FOR {JOIN|ORDER BY|GROUP BY}] (INDEX_LIST)
  | IGNORE {INDEX|KEY}
      [FOR {JOIN|ORDER BY|GROUP BY}] (INDEX_LIST)
  | FORCE {INDEX|KEY}
      [FOR {JOIN|ORDER BY|GROUP BY}] (INDEX_LIST)

INDEX_LIST:
    INDEX_NAME , INDEX_NAME ...

---

출처

https://choicode.tistory.com/27

[DB] 데이터베이스(DB) 인덱스(Index) 란 무엇인가?

https://ssocoit.tistory.com/217

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

https://gdlovehush.tistory.com/156

균형 이진 탐색 트리 (AVL트리)

 

https://rebro.kr/169

[DB] 10. B-Tree (B-트리)

 

https://velog.io/@bae_mung/TIL-MySQL-Hint

[TIL] MySQL Hint