DB

기술노트
Admin (토론 | 기여)님의 2025년 4월 17일 (목) 14:23 판 (CS 용어 정리 - DB 추가)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

DB

인덱스

인덱스는 데이터를 테이블에 검색 작업을 할때 성능을 높여주는 자료구조이다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 쿼리문에 "인덱스 생성 컬럼을 WHERE 조건으로 거는 등"의 작업을 하면 *옵티마이저에서 판단하여 생성된 인덱스를 탈 수가 있다. 만약 인덱스를 타게 되면 아래의 그림과 같이 인덱스를 타게 되고 먼저 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작을 하여 검색 속도의 향상을 가져올 수 있다.

또한 인덱스 생성시, 데이터를 오름차순으로 정렬하기 때문에 정렬된 주소체계라고 표현할 수 있다.

> 옵티마이저 : 옵티마이저는 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성해주는 DBMS의 핵심 엔진이다. > 컴퓨터의 두뇌가 CPU인 것처럼 DBMS의 두뇌는 옵티마이저라고 할 수 있다.

![index](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbPb8pb%2FbtrePWRO9HY%2FqrzMfX84KAAuFgkyZkKtKK%2Fimg.png)

인덱스의 사용이유

인덱스의 가장 큰 특징으로는 모든 데이터들이 정렬되어 있다는 점이다. 이 특징으로 조건 검색이라는 영역에서 굉장한 장점이 된다.

1. 조건 검색 WHERE 효율

  - 테이블을 만들고 안에 데이터가 쌓이게 되면 테이블의 레코드(row : 행)는 내부적으로 순서가 없이 뒤죽박죽으로 저장이 된다. 
  - 이렇게 되면 WHERE절에 특정 조건에 맞는 데이터들을 찾아낼 때도 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야 한다. 이것을 풀 테이블 스캔 (Full Table Scan), 줄여서 풀 스캔(Full Scan)이라고 한다. 
  - 만 인덱스 테이블 스캔(Index Table Scan) 시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건(WHERE)에 맞는 데이터들을 빠르게 찾아낼 수 있는 것이다

2. 정렬 ORDER BY 효율

  - 인덱스는 기본적으로 정렬이 되어오기 때문에 정렬 과정을 피할 수 있다.

3. MIN,MAX 효율 처리

인덱스의 단점

1. 인덱스는 DML에 취약하다.

  - INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다.
  - 그에 따른 추가 시간 소모

2. 무조건 인덱스 스캔이 좋은 것이 아니다.

   - 인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 낫다. 
   - 100개의 데이터가 있는 테이블과 100만 개의 데이터가 들어 있는 테이블이 있다고 하자. 100만 개의 데이터가 들어있는 테이블이라면 풀 스캔보다는 인덱스 스캔이 유리하겠지만, 100개의 데이터가 들어있는 테이블은 굳이 인덱스 스캔 없이 풀 스캔이 빠를 것이다

3. 속도 향상을 위해선 인덱스를 많이 만들지 않는 것이 좋다.

   - 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다

4. 전체적인 데이터베이스 성능 부하를 초래한다.

  - 데이터베이스 서버에 성능 문제가 발생하면 가장 빨리 생각하는 해결책이 인덱스 추가 생성이다.
    문제가 발생할 때마다 인덱스를 생성하면서 인덱스가 쌓여가는 것은 하나의 쿼리문을 빠르게는 만들 수 있지만,
    전체적인 데이터베이스의 성능 부하를 초래한다.

인덱스의 종류

HashTable

Key-Value 형태로 저장시키는 해쉬테이블을 이용한 자료구조로 빠른 데이터 탐색이 가능하다.

하지만, 해쉬 충돌과 등호 연산에 최적화되어 있는 자료구조의 특성상 추천되지 않는다.

B-TREE

트리구조로 구성되어 있는 자료구조로, DB 인덱스가 아니어도 검색이 유용한 구조로 자주 사용된다.

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqycZ2%2FbtqBQnr4QYG%2F7J8KpnmNaJiTjgS0K9TEIK%2Fimg.png)

여기서 B-Tree의 핵심은 데이터가 항상 정렬된 상태라는 점이다.

B-TREE의 구조는 크게 3가지로 나뉜다.

1. ROOT 2. BRANCH 3. LEAF

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fcikell%2FbtqBRvDU1xF%2FCdIhvg8XEhHKaP23vE4Ju1%2Fimg.jpg)

위의 사진을 보면 Binary Search Tree(이분 탐색 트리)와 비슷한 구조를 가지고 있으나 자식 노드로 2개 이상의 노드를 가질 수 있다는 점에서 차이가존재한다. 검색 방법은 `Key`값을 이용하여 찾고자하는 데이터를 찾는다.

B-TREE의 검색방법

1. 인덱스 레인지 스캔

  • 데이터를 이미 정렬 상태로 넣기 때문에 예를 들어 범위 검색을 통해 찾고자하는 값이 4이상이라면 아래의 그림과 같은 방법으로 4번 인덱스(1번 리프노드)는 거치지 않게된다.
  • B-TREE의 검색방법중 가장 빠른 속도를 보장하며 B-Tree의 필요한 영역을 스캔하는 데 어떤 작업이 필요한지만 이해할 수 있으면 충분하다.

![index_Range_Scan](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F2252D637592E6F432C)

  • 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
  • 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 실제로 원하는 시작 지점을 찾을 수 있다.
  • 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔합니다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.
  • 만약 3건의 레코드가 검색 조건에 일치했다고 가정하면 데이터 레코드를 읽기 위해 랜덤 I/O가 최대 3번이 필요하게 됩니다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류됨.
  • 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 되는 것

2. 인덱스 풀 스캔

  • 인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 일근 방식을 인덱스 풀스캔이라고 함
  • 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우 인덱스 풀스캔방식이 사용됩니다. 예를 들어 인덱스는 (A, B, C) 컬럼의 순서대로 만들어져 있지만 쿼리의 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경
  • 일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적
  • 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F236F1C3C592E6F580A)

3. 루스 인덱스 스캔

  • 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용

B-TREE는 왜 빠른가?

B-TREE의 장점은 한 가지 '어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다'인데, 이를 '균일성'이라고 한다. (트리 높이가 다른 경우, 약간의 차이는 있겠지만 O(logN)이라는 시간 복잡도를 구할 수 있다.)

B-TREE는 균형 트리 구조

![](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb9BMy3%2FbtqBTL7abid%2FXsBqjuQU9fMG9CdDakMMa1%2Fimg.png)

'균형 트리'란 루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻하는 것으로, 트리 중에서 특히 성능이 안정화 되어있다.

그러나, B-tree 처음 생성 당시는 균형 트리이지만 테이블 갱신(INSERT/UPDATE/DELETE)의 반복을 통해 서서히 균형이 깨지고, 성능도 악화된다.

어느 정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우 인덱스 재구성을 해서 트리의 균형을 되찾는 작업이 필요하다.

B+TREE

기존 B-TREE는 한 데이터의 검색은 효율적이지만, 모든 데이터를 순회하는데에 모든 노드를 순회해야하는 비효율적 구조를 띄고 있기에 단점을 개선시킨 B+TREE가 생겼다.

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다 그리고 leaf node끼리는 Linked list로 연결되어있다.

또, B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.

![B+TREE](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FSvp6z%2FbtrdEi9c2DR%2FR4Dnmqkl8RWcqQPBACI9fK%2Fimg.png)

B+TREE 장점

1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.

2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.

3. B-TREE와 비교하여, B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있다.

해시 테이블에서 언급했듯이 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 된다.


B+Tree의 검색 과정은 B-Tree와 동일하다.

반면 B+Tree의 삽입과 삭제 과정은 약간의 차이가 있다. 기본적으로 B+Tree의 삽입과 삭제는 항상 leaf node에서 일어난다.

인덱스가 효율적인 이유와 대수 확장성

인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형잡힌 트리 구조와 트리 깊이의 대수확장성 떄문이다.

다만 B-TREE의 경우 비균형 트리가 될 수 있으며, 깊이 또한 키값의 크기에 따라 달라진다.

키값이 16바이트인 경우 최대 2억 32바이트인 경우 5천만개로 줄어든다.

대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미한다. 기본적으로 인덱스가 한깊이 씩 증가할 때마다, 최대 인덱스 항목의 수는 4배씩 증가한다.

인덱스 생성방법

MySQL MySQL의 경우 클러스터형 인덱스와 세컨더리 인덱스가 존재한다.

클러스터형 인덱스

  • 하나의 키를 기반으로 물리적으로 테이블의 데이터 행을 정렬 및 저장한다.
  • 클러스터 인덱스는 데이터를 가리키는 포인터가 아닌 데이터를 저장한 블록의 포인터를 저장한다.
  • 테이블 당 하나만 생성가능
  • 인덱스 자체의 리프 노드가 곧 데이터다. 즉 테이블 자체가 인덱스이다.
  • 데이터 입력, 수정, 삭제 시 항상 정렬 상태를 유지한다.

비클러스터형 인덱스(세컨더리 인덱스)

  • 테이블당 약 240개의 인덱스를 만들 수 있다.
  • 인덱스 페이지는 로그파일에 저장된다.
  • 레코드의 원본은 정렬되지 않고, 인덱스 페이지만 정렬된다.
  • 인덱스 자체의 리프 페이지는 데이터가 아니라 데이터가 위치하는 포인터(RID)이기 때문에 클러스터형보다 검색 속도는 더 느리지만 데이터의 입력, 수정, 삭제는 더 빠르다.
  • 인덱스를 생성할 때 데이터 페이지는 그냥 둔 상태에서 별도의 인덱스 페이지를 따로 만들기 때문에 용량을 더 차지한다
  • 3% 이내에서 사용해야 좋은 선택도를 가진다.

클러스터 인덱스와 비 클러스터 인덱스 비교

|기준|클러스터 인덱스|비 클러스터 인덱스| |----|-------|--------| |속도|빠르다|느리다| |사용 메모리|적다|많다 |인덱스|인덱스가 주요 데이터|인덱스가 데이터의 사본(Copy)| |개수|한 테이블에 한 개|한 테이블에 여러 개(최대 약 250개)| |리프 노드|리프 노드 자체가 데이터|리프 노드는 데이터가 저장되는 위치| |저장값|데이터를 저장한 블록의 포인터|값과 데이터의 위치를 가리키는 포인터| |정렬|인덱스 순서와 물리적 순서가 일치|인덱스 순서와 물리적 순서가 불일치|

조인의 종류

조인은 두 개이상의 테이블을 묶어 하나의 결과 집합으로 만들어내는 것입니다.즉, 서로 다른 테이블에서 데이터를 가져올 때 사용하는 것이 조인(Join)입니다.

이러한 Join은 총 3가지의 join이 주로 사용됩니다.

Inner Join(내부 조인)

  • 조인 중 가장 흔히 사용되는 조인입니다. 기본적으로 아래와 같은 쿼리문을 사용할 때도 Inner JOIN이 사용됩니다.

USE shopDB SELECT * FROM buyTBL JOIN userTBL ON buyTBL.userID = userTBL.userID WHERE buyTBL.userID = 'LEE'; Inner Join은 대부분 두 table의 교집합을 얘기합니다. 예시로 A와 B가 있다면 A와 B의 교집합을 가져옵니다.

A B

  • -

1 3 2 4 3 5 4 6 위와 같은 테이블이 있다면 Inner Join 작업 수행시 3과 4만이 해당하므로 (3,4)만 결과값으로 도출됩니다.

Outer Join

반대되는 개념인 Outer Join은 합집합을 가져오게된다. Outer Join에는 총 3가지의 종류가 존재한다.

Left, Right, Full이다.

Left와 Right는 A와 B를 기준으로 Join할 때 Left Join의 경우 A를 기준으로 합집합을 만든다는 것이고, Right Join의 경우 B를 기준으로 합집합을 만드는 것이다. Full outer Join의 경우 A와 B의 컬럼을 모두 출력하는 합집합을 만든다.

LEFT outer Join select * from a LEFT OUTER JOIN b on a.a = b.b; select a.,b. from a,b where a.a = b.b(+);

a | b --+----- 1 | null 2 | null 3 | 3 4 | 4 Right outer Join select * from a RIGHT OUTER JOIN b on a.a = b.b; select a.,b. from a,b where a.a(+) = b.b;

a | b


+----

3 | 3 4 | 4 null | 5 null | 6 Full outer Join select * from a FULL OUTER JOIN b on a.a = b.b;

a | b


+-----

1 | null 2 | null 3 | 3 4 | 4 null | 6 null | 5 흔히들 알고있는 inner와 outer외에도 CROSS JOIN(상호 조인)이 있습니다.


CROSS JOIN

CROSS JOIN은 한쪽 테이블의 행 하나당 다른 쪽 테이블의 모든 행을 하나씩 모든 행들을 각각 조인합니다.

즉, A 테이블의 1번 행을 B 테이블의 1번 행에 조인 시키고, 다음은 A 테이블의 1번 행을 B 테이블의 2번 행에 조인시키고 ...생략... 이를 모든 A 테이블의 행에 각각 모든 B 테이블의 행들에 조인합니다. CROSS JOIN의 결과 행의 개수는 [A 테이블 행의 개수 X B 테이블 행의 개수]가 됩니다.

CROSS JOIN은 카티션 곱(Catesian Product)이라고도 부릅니다

SELECT * FROM ATable CROSS JOIN BTable; 기본적인 CROSS JOIN 구문입니다. INNER과 OUTER 조인과 달리 ON 구문은 사용하지 않습니다. SELECT * FROM ATable, BTable; 형식으로 작성할 수도 있는데 호환성 등의 이유로 권장되지 않습니다.

SELF JOIN(자체 조인)은 자신에게 조인하는 것입니다. 같은 테이블에 두 번 참조해야 하는 경우도 있습니다.


조인 수행원리

조인이란 두 개 이상의 테이블을 하나의 집합으로 만드는 연산이다. SQL문에서 FROM 절에 두 개 이상의 테이블이 나열될 경우 조인이 수행된다. 조인 연산은 두 테이블 사이에서 수행된다. FROM 절에 A, B, C라는 세 개의 테이블이 존재하더라도 세 개의 테이블이 동시에 조인이 수행되는 것은 아니다. 세 개의 테이블 중에서 먼저 두 개의 테이블에 대해 조인이 수행된다. 그리고 먼저 수행된 조인 결과와 나머지 테이블 사이에서 조인이 수행된다. 이러한 작업은 FROM 절에 나열된 모든 테이블을 조인할 때까지 반복 수행한다. 예를 들어, A, B, C 세 개의 테이블을 조인할 때를 가정으로 설명하면 다음과 같다. 먼저 A와 B 두 테이블을 먼저 조인하면 해당 조인 결과와 나머지 C 테이블을 조인한다(A → B → C). 만약, A와 C 테이블을 먼저 조인한다면 해당 조인 결과와 나머지 B 테이블을 조인한다(A → C → B). 테이블 또는 조인 결과를 이용하여 조인을 수행할 때 조인 단계별로 다른 조인 기법을 사용할 수 있다. 예를 들어, A와 B 테이블을 조인할 때는 NL Join 기법을 사용하고 해당 조인 결과와 C 테이블을 조인할 때는 Hash Join 기법을 사용할 수 있다. 조인 기법은 두 개의 테이블을 조인할 때 사용할 수 있는 방법이다. 여기서는 조인 기법 중에서 자주 사용되는 NL Join, Hash Join, Sort Merge Join에 대해서 조인 원리를 간단하게 설명한다.

NL Join

NL Join은 프로그래밍에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행한다. 반복문의 외부에 있는 테이블을 선행 테이블 또는 외부 테이블(Outer Table)이라고 하고, 반복문의 내부에 있는 테이블을 후행 테이블 또는 내부 테이블(Inner Table)이라고 한다.


FOR 선행 테이블 읽음 → 외부 테이블(Outer Table) FOR 후행 테이블 읽음 → 내부 테이블(Inner Table) (선행 테이블과 후행 테이블 조인)

먼저 선행 테이블의 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행한다. 이 작업은 선행 테이블의 조건을 만족하는 모든 행의 수만큼 반복 수행한다. NL Join에서는 선행 테이블의 조건을 만족하는 행의 수가 많으면(처리 주관 범위가 넓으면), 그 만큼 후행 테이블의 조인 작업은 반복 수행된다. 따라서 결과 행의 수가 적은(처리 주관 범위가 좁은) 테이블을 조인 순서상 선행 테이블로 선택하는 것이 전체 일량을 줄일 수 있다. NL Join은 랜덤 방식으로 데이터를 액세스하기 때문에 처리 범위가 좁은 것이 유리하다.

NL Join의 작업 방법은 다음과 같다. 1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음 2. 테이블의 조인 키 값을 가지고 후행 테이블에서 조인 수행 3. 선행 테이블의 조건을 만족하는 모든 행에 대해 1번 작업 반복 수행

HashJoin

Hash Join은 해슁 기법을 이용하여 조인을 수행한다. 조인을 수행할 테이블의 조인 칼럼을 기준으로 해쉬 함수를 수행하여 서로 동일한 해쉬 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행한다. Hash Join은 NL Join의 랜덤 액세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결 위한 대안으로 등장하였다.