TL;DR

• 인덱스 : 테이블에 대한 동작의 속도를 높여주는 자료 구조
• 결합 인덱스(다중 컬럼 인덱스) : 두 개 이상의 필드를 조합해서 생성한 INDEX
• ORDER BY와 GROUP BY를 위한 인덱스
• B-Tree
• B+Tree
• Join

인덱스 Index

• 인덱스는 추가적인 저장 공간을 사용해 DB의 검색 속도 향상을 위한 자료구조

• 인덱스는 MYI(MySQL Index)파일에 저장되며,

  인덱스가 설정되지 않았다면 Table Full Scan이 일어나 대용량 데이터엔 비효율적

• DBMS는 INDEX를 다양한 알고리즘으로 관리하고 있는데, 일반적으로 사용하는 알고리즘은 B+Tree 알고리즘

단점

• 약 10% 정도의 추가 저장 공간이 필요하다. (인덱스 테이블)

• 인덱스는 항상 정렬된 상태를 유지하기 때문에 탐색은 빠르지만 값을 추가(Insert), 삭제(Delete), 수정(Update)하는 경우에는 불리하다.

  => 추가, 삭제, 수정을 빈번하게 하는 경우에는 성능 저하가 올 수 있다.

INDEX 설계 시 고려할 점

• 무조건 많이 설정하지 않는다. (한 테이블당 3~5개가 적당 목적에 따라 상이)

• 인덱스 컬럼 선택 시 Cardinality 가 높은 컬럼 사용 (중복도가 가장 낮은 컬럼)

INDEX는 어떻게 동작하는가?

• SCOUNTER TABLE 생성 시 AIRPORT 컬럼에 대한 인덱스를 주면 AIRPORT 컬럼에 대한 인덱스 테이블이 생성된다.
• 그리고 나중에 SCOUNTER 테이블에 AIRPORT 컬럼에 대한 WHERE문이 포함된 쿼리가 나갈 때,
• AIRPORT 인덱스 테이블에 저장된 key-value 값을 참조해서 SCOUNTER TABLE 테이블에서 결과 값을 반환해온다.

1. Index Table에서 where에 포함된 값을 찾음
2. 해당 컬럼의 인덱스 테이블에 저장된 key-value 값을 참조
3. 가져온 인덱스 테이블에 저장된 key-value 값으로 원본 테이블에서 값을 조회해옴

INDEX 종류

키에 따른 인덱스 분류

• 기본 인덱스(Primary Index): 기본키를 포함하는 인덱스(키의 순서가 레코드의 순서를 결정)
• 보조 인덱스(Secondary Index): 기본 인덱스 이외의 인덱스

파일 조직에 따른 인덱스 분류

• Clustered Index
  • 데이터 레코드의 물리적 순서가 그 파일에 대한 인덱스 엔트리 순서와 동일하게 유지되도록 구성된 인덱스
  • Mysql의 경우 PK 설정시, 기본적으로 PK를 기준으로 Clustered Index 생성
  • 테이블당 한 개를 만들 수 있다.
• Unclustered Index
  • 파일 인덱스 엔트리 순서가 데이터 레코드의 물리적 순서와 일치하지 않음.
  • 파일 인덱스 엔트리의 리프 노드에는 해당 레코드의 주소값이(실제 값X) 들어가 있음
  • 물리적으로 데이터를 정렬하지 않는 대신 위치정보를 인덱스로 구성

결합 인덱스(다중 컬럼 인덱스)

• 다중 컬럼 인덱스는 두 개 이상의 필드를 조합해서 생성한 INDEX
• 주 용도는 SQL에서 WHERE절의 조건 컬럼이 2개 이상 AND로 연결되어 함께 사용되는 경우에 많이 사용
• 다중 컬럼 인덱스는 단일 컬럼 인덱스 보다 더 비효율적으로 INDEX/UPDATE/DELETE를 수행하기 때문에 신중해야한다.

SELECT * FROM table1 WHERE name='홍길동' AND address='경기도';

예를 들어 위와 같은 쿼리가 있을 때,

• 단일 컬럼 인덱스 테이블의 경우,

  인덱스가 걸린 여러 컬럼 중 더 빠르게 검색 되는지 판단한 후에 해당 컬럼을 이용해 검색

• 다중 컬럼 인덱스 테이블의 경우,

  key idx(name, address) 이렇게 저장되었다면 한번에 ‘‘홍길동경기도’‘로 검색 가능

결합 인덱스 타는 경우 / 안 타는 경우

• 다중 컬럼 인덱스 사용할 때는 INDEX로 설정해준 제일 왼쪽 컬럼이 WHERE 절에 사용되어야 한다. (B+Tree 자료구조 탐색 기준)

• 순서대로 적용되기 때문에 중간 인덱스가 빠지면 인덱스 적용이 안된다.

  (name, address, age) 에서 name 과 age 만 WHERE 절에 있다면 age는 인덱스 적용이 안됨

• 따라서 결합 인덱스는 Cardinality 가 높은 순서대로 내림차순으로 적용하는게 성능상 제일 좋다.

ORDER BY 와 GROUP BY에 대한 INDEX

INDEX는 ORDER BY와 GROUP BY에도 영향을 끼치는데 다음과 같은 경우에는 INDEX를 타지 않는다.

• 연속하지 않은 컬럼에 대해 ORDER BY를 실행한 경우
  • ORDER BY도 똑같이 B*Tree 자료구조 탐색 조건에 위배되지 않아야 인덱스가 걸림
• DESC와 ASC를 혼합해서 사용한 경우
  • 정렬되는 각 컬럼의 오름차순 및 내림차순 옵션이 인덱스와 같거나 정반대인 경우에만 사용가능
• GROUP BY와 ORDER BY의 컬럼이 다른 경우
• ORDER BY 절에 다른 표현을 사용한 경우

인덱스 조회시 주의 사항

범위 조건(LIKE, BETWEEN, <, >)과 INDEX

between, like, <, > 등 범위 조건은 해당 컬럼은 인덱스를 타지만, 그 뒤 인덱스 컬럼들은 인덱스가 사용되지 않습니다.

• group_no, from_date, is_bonus으로 인덱스가 잡혀있다고 가정하겠습니다.

• 조회 쿼리를 아래로 잡으면 is_bonus는 인덱스가 사용되지 않습니다.

  where group_no=XX and is_bonus=YY and from_date > ZZ
  

  • 중간에 from_date에서 범위 탐색을 함으로써 인덱스가 먹히지 않음

=, in과 INDEX

• =, in 은 다음 컬럼도 인덱스를 사용합니다.
  • 왜냐면 in은 결국 =를 여러번 실행시킨 것이기 때문입니다.
  • 단, in은 인자값으로 상수가 포함되면 문제 없지만, 서브쿼리를 넣게되면 성능상 이슈가 발생합니다.

컬럼값 가공금지

• 인덱스는 가공된 데이터를 저장하고 있지 않습니다.
• 인덱스로 사용된 컬럼값 그대로 사용해야만 인덱스가 사용됩니다.
  • where salary * 10 > 150000;는 인덱스를 사용하지 않습니다.
  • 하지만, where salary > 150000 / 10;는 인덱스를 사용합니다.
  • ABS(컬럼) 이런것도 인덱스가

null 값의 경우

• null 값의 경우 is null 조건으로 인덱스 레인지 스캔 가능

OR 조건

• AND 연산자는 각 조건들이 읽어와야할 ROW 수를 줄이는 역할을 합니다.
• 하지만 OR 연산자는 비교해야할 ROW가 더 늘어나기 때문에 풀 테이블 스캔이 발생할 확률이 높습니다.

B-Tree, B+Tree

B-Tree

B-트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조. 이진 트리와는 다르게 하나의 노드에 많은 정보를 가질 수 있습니다. 이렇게 하나의 노드에 여러 정보를 담게 되면서 차수라는 개념이 등장합니다.

• 이진 트리를 확장시켜 2개 이상의 자식을 가질 수 있게 일반화한 자료구조

• 허용하는 자식 노드가 최대 M개라면 M차 B-Tree라고 부릅니다.

• 따라서 아무리 최악의 경우라도 O(logN)의 검색 성능을 보여줍니다.

B-트리 모양의 특징(6가지)

1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
2. 모든 노드는 최대 M개의 자식을 가진다.

3. 모든 노드는 키와 자식 노드에 대한 포인터로 이루어져있다.

4. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.

5. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key 보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.

6. 노드 내에 데이터는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다

7. 모든 리프 노드들이 같은 레벨에 존재한다.

   즉, 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.

B-트리 탐색 과정

B-트리는 루트 노드에서 탐색을 시작하여 하향식으로 탐색을 진행한다. 찾고자 하는 값이 K라면 다음과 같은 과정을 거친다.

1. 루트 노드에서 탐색을 시작한다.
2. K를 찾았다면 탐색을 종료한다.
3. K와 노드의 key값을 비교해 알맞은 자식 노드로 내려간다.
4. 해당 과정을 리프 노드에 도달할 때까지 반복한다.
5. 리프 노드에서도 K를 찾지 못한다면 트리에 값이 존재하지 않는 것

B-트리 삽입 과정

B-트리에 데이터를 삽입하는 과정은 탐색과는 다르게 상향식으로 진행된다. B-트리에서의 데이터 삽입은 항상 리프 노드에서 시작된다.

1. 해당원소가 들어 가야 할 리프노드를 찾는다.
2. 노드에 빈 자리가 있다면 새로운 원소를 삽입한다.
3. 노드에 빈 자리가 없다면 노드를 2 개로 분할한다.
4. 기존 노드의 원소와 새로운 원소 중에 중간 값을 분할된 부모 노드의 값으로 한다.
5. 중간 값보다 작은 값은 왼쪽 노드로 큰 값은 오른쪽 노드에 넣는다
6. 중간 값을 부모 노드로 넣을 때, 부모 노드에 자리가 없으면 부모 노드도 위의 규칙에 의해 분할한다

적절한 상태? 적절한 상태란, 해당 노드의 데이터 개수가 허용 범위 안에 있는 것을 의미. 반대로 부적절한 상태란 해당 노드의 데이터 개수가 허용 범위를 벗어나 너무 많은 상태를 뜻한다.

• 참고: [자료구조] B-트리(B- Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

B트리 삭제 과정

삭제 과정중에서도 아래와 같은 조건을 만족해야 하며, 조건이 위반되면 트리를 재구조화 한다.

1. 내부 노드(루트가 아닌 노드)는 M/2 ~ M개의 자식 노드를 가질 수 있다.
2. 각 노드는 floor(M/2)-1 ~ M-1 개의 데이터(key)를 가질 수 있다.
3. 노드의 key가 K개 라면 자식 노드의 개수는 K+1개여야 한다.

• 참고: [자료구조] B-트리(B- Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

B+트리

B+트리란?

• B-tree 확장 개념으로, 브랜치 노드에 key만 담아두고, 오직 리프 노드에만 key와 data를 저장.
• B-tree는 탐색을 위해 노드를 찾아서 이동해야 한다는 단점을 가지고 있는데, 이 단점을 해소하고자 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 sibiling node는 연결리스트 형태로 이어져 있다.
• 리프노드끼리 Linked list로 연결되어 있다.

B-트리의 특징을 가지고 있지만, 모든 키 값들이 리프 노드에 정렬되어있는 트리 구조 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있는 자료 구조(선형 검색 가능)

• Index node들과 Data node(레코드)로 구성이 되어있다.
  • Index node: leaf node를 제외한 나머지 node. 인덱스 노드의 value에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재
  • Data node: leaf node. 오직 리프노드에만 key와 data를 저장하고, 리프 노드끼리 연결 리스트로 연결. 데이터 노드의 value에는 데이터가 존재

B+트리 의의

B-트리는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있습니다. 이러한 단점을 해소하고자 B+트리는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Leaf node는 연결리스트 형태로 이어져 있습니다.

• 그래서 풀 스캔이 필요하다면 leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 연결되어 있으므로 탐색에 있어서 매우 유리합니다.
• 오늘날 DB에서 제일 중요한 건 검색속도이기 때문에 대부분의 DB 시스템은 B+Tree 구조를 채택하고 있습니다.(ex. Mysql InnoDB)

B+트리 장단점

장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key를 수용할 수 있다.
   • 하나의 노드에 더 많은 key를 담을 수 있기 때문에 트리의 높이는 더 낮아진다.
   • B+트리의 높이는 B-트리 보다 낮게 구성되므로 검색시간과 디스크에 접근하는 횟수가 줄어든다
2. 풀 스캔 시, B+트리는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-트리에 비해 빠르다.
   • B-트리의 경우에는 모든 노드를 확인해야 한다.

단점

• B-트리의 경우 best case에는 루트에서 끝날수 있지만, B+트리의 경우 무조건 leaf노드까지 가야한다.

B-트리와 B+트리 비교

• 아래 표에서 말하는 데이터는 자료구조 상 value에 해당 (실제 DB 데이터가 X)

조인

• Inner Join : 서로 연관된 내용만 검색하는 조인 방법
• Left outer join
• Right outer join : 한 쪽에는 데이터가 있고 한 쪽에는 데이터가 없는 경우, 데이터가 있는 쪽의 내용을 전부 출력하는 방법
• Full outer join
• Cross join

물리적인 JOIN

• Nested Loop Join (중첩 반복 조인)

  • 2개 이상의 테이블에서 하나의 테이블을 기준으로 순차적으로 상대방의 row 를 결합해 원하는 결과를 추출하는 방법

  • Driving Table의 처리 범위를 하나씩 액세스 하면서 추출된 값으로 Driven Table을 조인하는 방식으로 동작

    • 선행 테이블(Driving Table) : 조인 시 먼저 액세스 되는 테이블

      ​ WHERE 절로 최대한 데이터를 거를 수 있는 테이블 / 데이터 양이 적은 테이블로 선정

      후행 테이블(Driven Table) : 조인 시 나중에 액세스 되는 테이블 (Driving이 아닌 나머지 테이블)

      ​ 조인을 위한 인덱스가 생성되어 있는 것이 좋다

      ​ ( 없다면 Driving Table에서 도출된 결과와 맞는지 매번 FULL TABLE SCAN으로 일일이 비교해야 하기 때문)

• Merge Join (정렬 병합)

  • 양 테이블에 각각 접근해 결과를 정렬하고, 정렬한 결과를 scan 하면서 연결 조건으로 merge
  • 각 테이블에 대해 동시에 독립적으로 데이터를 먼저 읽고,
  • 읽혀진 각 테이블의 데이터를 조인을 위한 연결고리에 대해 정렬을 수행,

  • 정렬이 끝난 후 조인 작업 수행

  • 사용하는 경우

    1. 두 join 열을 미리 정렬된 상태로 가져올 수 있는 경우

    2. 연결 고리에 인덱스가 전혀 없는 경우

    3. 대용량의 자료를 조인할때 유리한 경우

    4. 조인 조건으로 <, >, <=, >=와 같은 범위 비교 연산자가 사용된 경우

    5. 인덱스 사용에 따른 랜덤 액세스의 오버헤드가 많은 경우

Join이란?

관계형 데이터베이스에서 두 개 이상의 테이블을 연결하여 데이터를 검색하는 방법. 여러 개의 테이블을 하나인 것처럼 활용한다.

Nested-Loop-Join(Join 동작 원리)

Table A: Driving Table 혹은 Outer Table이라고 함

Table B: Driven Table 혹은 Inner Table이라고 함

# 등가조인[Equi Join]
# SELECT * FROM 테이블1, 테이블2
#	 WHERE 테이블명1.컬럼명1=테이블명2.컬럼명2;

SELECT E.ENAME, D.DNAME
FROM EMP E, DEPT D
WHERE E.DEPTNO = D.DEPTNO
;

1. Table A에서 row를 하나씩 반복해가며 스캔한다.

2. Driving Table의

   row 하나 마다
   

   반대편

   Driven Table의 레코드를 하나씩 스캔
   

   해서 Join 조건에 맞으면 데이터를 찾아서 가져온다.

   • 선행 테이블에서 row를 가져온 후 조인 조건절(등가조인이므로 WHERE절)을 검사해서 동일한 조건을 가진 레코드면 후행 테이블에서 가져옴.

3. 1~2 과정을 Driving Table의 모든 row에 대해 반복

Nested Loop의 실행시간

• Table A의 Row 개수 * Table B의 Row 개수 = Nested Loop의 실행 시간
• R(A) * R(B) = 실행시간 인데, R(A) * R(B) == R(B) * R(A)
• 여기서 재밌는 사실을 알 수 있습니다.
• Driving Table이 무엇이 되었든 조회결과는 R(A) * R(B), R(B) * R(A)이므로 동일함
• 그런데 우리는 Driving Table은 작은걸 선택해야 성능이 좋아진다는 이야기를 많이 들었습니다.
• 이 이야기에는 1개지 대전제가 있습니다.

바로, “Driven Table(Table B)의 조인 키는 인덱스가 걸려 있어야 한다” 임

• 일반적으로 조인은 FK를 통해 이루어지므로 위 대전제를 신경쓰지 않고 수행할때가 많음.
• 반대로 Fk를 비롯한 인덱스가 전혀 없는 컬럼을 통해 조인을 실행하면 Driving Table이 어떤것이 되었든 실행시간은 비효율적으로 나타납니다.
• 꼭 숙지해야할 내용은 이 한줄인것 같습니다.

Row가 적은 Driving Table + Driven Table의 조인키에는 인덱스가 걸려있어야 GOOD

예상질문

• DB 인덱스에 대해서 설명해주세요(DB 인덱스는 무엇인가요?)
• 인덱스를 구현하는 방식에서 B+트리를 사용하는 방식과 해시를 사용하는 방식의 차이는 무엇일까요?
• 테이블에 설정될 수 있는 인덱스 형태들에는 어떤 것들이 있나요?
• Join 내부 동작 방식에 대해 알고 있나요?
• inner join vs outer join 차이는?

##

질문

• 인덱스를 사용할 때 유리한 경우는 언제일까요?
• 인덱스를 사용할 시 단점은 무엇일까요?
• DBMS는 Index를 어떻게 관리하고 있나요?

1. (몰라서 질문드려요) 기본 인덱스와 클러스터링 인덱스의 차이는 무엇인가요? 보조 인덱스와 언클러스터링 인덱스의 차이는 무엇인가요?
2. 데이터 갱신시 결합 인덱스는 단일컬럼 인덱스보다 왜 더 비효율적인가요?
3. Nested Loop의 실행시간을 줄일 수 있는 방법에는 어떤 것이 있을까요?
4. B+ 트리 꼬리질문
5. 인덱스 꼬리질문

References