👋 들어가기 전
이번 포스팅은 DB의 검색 속도를 향상시킬 때 필수적으로 등장하는 Index라는 개념에 대해 알아보자.
iOS 개발자지만 항상 Backend 쪽 개념도 궁금했기 때문에 이번 기회에 한달에 한번이라도
백엔드 쪽 개념도 같이 살펴보는 습관을 가지면 좋을 것 같다.
이번 시간도 역시 🍎 코딩 애플님의 유튜브 영상과 함께 공부해보자.
❓ 왜 필요할까??
만약 1 ~ 10 사이에서 특정 숫자를 찾고 싶으면 시간이 얼마나 걸릴까 ?? 한 숫자를 살펴보는데 1초 거린다고
가정하면 최대 10초가 걸린다. 만약 10이 아니라 10억이면 10억초가 걸리는건다. 물론 실제로는 그렇지 않지만
위 탐색은 가장 무난한 선형 탐색을 의미한다. T(n) = O(n)
그렇다면 탐색 알고리즘을 바꿔보자. 이진 탐샘으로 바꿔보면 어떨까?? T(n) = O(nlogn)
성능이 정말 많이 갱신되었다 😀 하지만 여기는 큰 전제 조건이 있는데 바로 정렬이다.
이진 탐색은 정렬이 되있어야 가능하다.
이 전제 조건을 위해 인덱스라는 자료구조가 탄생하게 된다.
⭐️ 정의
영어로 인덱스는 색인이라는 뜻을 갖고 있으며 현실에서는 책 또는 가이드 라인의 앞 부분에
목차로 사용된다.
색인과 목차는 무슨역할을 했을까?? 바로 원하는 자료를 빠르게 찾게 도와주는 역할을 담당했다.
데이터 베이스에서도 역시 같은 역할을 한다.
⭐️ 특징
1. 인덱스는 정렬된 column이다.
실제 데이터는 정렬되어있지 않지만 우리는 처음에 본 것처럼 빠른 탐색을 위해서는 정렬된 데이터가 있어야한다.
정렬된 데이터가 바로 인덱스다.
2. 인덱스는 별도의 메모리가 필요하다.
인덱스는 실제 데이터와 별도로 관리가 되야하므로 별도의 메모리로 할당되어 관리된다.
3. 인덱스를 효율적으로 사용하기 위한 조건
a. 규모가 크지않은 테이블
b. INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- 인덱스는 INSERT 연산에 추가되고, DELETE와 UPDATE 때 기존 인덱스를 갱신한다
- 이 때 INSERT, UPDATE, DELETE가 자주 발생하는 컬럼일 경우 계속 인덱스를 갱신하므로 성능이 오히려 떨어진다.
c. JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼에 사용한다.
d. 데이터 중복도가 낮은 컬럼에 사용한다.
⭐️ 장/단점
장점
- 검색 속도와 성능을 향상 시킨다.
- 검색에 들어가는 부하를 줄여준다.
단점
- 인덱스 관리를 위해 DB의 10%를 사용한다.
- 인덱스 관리를 위해 별도의 작업이 필요하고 또한 잘못 사용할 경우 오히려 성능을 떨어 트릴 수 있다.
🧪 원리
인덱스는 B-Tree 또는 B+Tree로 관리된다.
먼저 B-Tree 부터 알아보자.
B-Tree
B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 저장할 수 있으며 최대 M개의 자식을
가질 수 있는 트리를 M차 B-트리라고 한다.
노드이 자식의 갯수를 child(node) , 노드의 키의 개수를 key(node)라고 할 때
M차 B- 트리는 다음과 같은 특징은 갖는다
- round(M/2) <= child(node) <= M (최소 조건에서 루트와 leaf 노드는 제외)
- round(M/2)-1 <= key(node <= M-1 (최소 조건에서 루트 노드는 제외)
- internal 노드의 KEY가 n개라면 자식 노드의 수는 언제나 n+1개 이다.
- 노드의 KEY들은 항상 정렬된 상태로 저장된다.
아래 그림은 3차 B-트리다.
여기서 파란 부분은 Key (노드의 데이터 값), 빨간 부분은 child 노드를 가르키는 포인터다.
각 특징이 맞는 지 살펴보자.
M = 3
1. 노드의 자식은 최대 3개, 최소 2개 이상은 갖고 있다.
2. 각 노드의 키는 최대 2개, 최소 1개의 key를 갖는다.
3. internal 노드에서 14, 17 노드를 보면 key가 2개이기 때문에 자식은 2+1인 3이된다.
4. 왼쪽 트리부터 오른쪽 까지 정렬이 되어있다.
B+Tree
B+트리는 B트리와 뭐가 다를까 ??
구조적으로는 리프노드에 연결리스트를 사용해 선형 검색 기능을 추가한 것
그림으로 보면 아래와 같다.
B트리와의 차이점을 알아보자.
- B트리는 각 노드마다 key와 data를 갖지만 B+트리는 리프노드에 key와 data가 모여있다.
- B트리에서는 다른 리프노드에 가기위해서는 다시 루트부터 탐색야하지만 B+트리의 리프노드에 연결리스트 구조가 있어
다른 리프노드로 선형 탐색이 가능하여 시간복잡도가 줄어듭니다.
😀 소감 및 마무리
실제로 DB에 index를 적용해보지는 않았지 원리를 이해하는데는 어렵지 않았다.
사이드로 백엔드를 할 기회가 있고 위에서 배운대로 index가 필요하다면 꼭 적용해봐야겠다.
출처
B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정
B 트리, 자료구조, 데이터 베이스
velog.io