![[DB] Index & B-Tree](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F33Fwp%2FbtrNSX1xOr1%2FEWUkHNaR9ohj9yIWRsusm1%2Fimg.jpg)
데이터베이스 인덱스는 왜 B -Tree 자료 구조를 선택하였는가?
해당 이유를 확인하기 전에 우선 인덱스에 대해 알아보자.
인덱스란 DB 내 저장된 데이터의 '주소'를 갖고 있는 것이다.
대용량 데이터를 담고 있는 데이터베이스에서 필요한 데이터를 빨리 찾으려면 인덱스가 필요하다.
인덱스는 DB 데이터 조회 성능 향상을 위해 사용된다.
만약 인덱스가 없으면 특정 값을 찾기 위해 모든 데이터 페이지를 확인하는 TABLE SCAN이 발생한다.
TABLE SCAN : 테이블에 읽는 모든 레코드를 순차적으로 읽는 것
Index 장단점
1. 장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
2. 단점
- 인덱스를 관리하기 위해 DB의 추가 저장 공간이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
- 인덱스를 관리하기 위한 추가 작업이 필요하다.
인덱스는 데이터 조회(SELECT)를 제외한 모든 동작,
즉, INSERT / UPDATE / DELETE 성능에 영향을 미친다.
위 세 가지 동작은 데이터를 삽입하고 수정하고 삭제하는데,
그러한 행위들로 인해 인덱스를 걸어둔 컬럼의 데이터가 바뀌면 인덱스 테이블의 수정도 필요하기 때문에,
데이터의 삽입 / 수정 / 삭제 작업의 두 번 이루어지게 되는 것이다.결론적으로,
RDBMS(관계형 데이터베이스 관리 시스템)에서 Index는 필수다.
일반적인 OLTP(OnLine Transaction Processing, 온라인 트랜잭션 처리) 시스템에서
데이터 조회 업무가 90% 이상이기 때문이다.
OLTP: On-Line Transaction Processing (데이터 갱신위주)
: 네트워크 상의 여러 이용자가 실시간으로 데이터베이스의 데이터를 갱신하거나 조회하는 등의 단위작업을 처리하는 방식
조회 업무의 검색 속도 향상은 시스템 부하를 감소시켜, 같은 시간 내에 더 많은 업무 처리가 가능해진다.
그렇기 때문에 인덱스를 사용하면 좋은 케이스는 아래와 같다.
(1) 규모가 작지 않은 테이블에서
(2) INSERT / UPDATE / DELETE가 자주 발생하지 않는 컬럼
(3) JOIN / WHERE / ORDER BY에 자주 사용되는 컬럼
(4) 데이터의 중복도가 낮은 컬럼
B-Tree 알고리즘
DBMS는 INDEX를 다양한 알고리즘으로 관리를 하고 있는데 일반적으로 사용되는 알고리즘은 B - Tree 알고리즘이다.
먼저, Tree 자료구조에 대해서 알고 가야한다.
일반적으로 Tree는 탐색하는 시간 복잡도가 O(longN)을 갖는다.
그러나 일반적이지 않고, 특수한 경우 (트리 노드의 요소가 한 쪽에 쏠릴 경우)에는 시간 복잡도가 O(N)을 갖게 되어 List와 별반 다를 것이 없다. 이러한 경우를 방지하기 위해 인덱스에서는 밸런스 트리 (B - Tree)를 선택하였다.
밸런스 트리 (B - Tree)란 트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어
왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다.
항상 양쪽 자식의 밸런스를 유지하므로 무조건 O(longN)의 시간 복잡도를 갖는다.
하지만, 노드 삽입 및 삭제 시 발생하는 재정렬 작업 때문에 탐색을 제외한 작업에서는 일반 Tree보다 성능이 좋지않다.
😈 인덱스의 자료 구조에서 해시 테이블보다 B - Tree가 더 선호되는 이유?
해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다.
해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조다.
해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치)로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다. 그 이유는, 해시 테이블은 등호(=) 연산에 최적화되어있기 때문이다.
데이터베이스에선 부등호(<, >) 연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 데이터베이스 검색색에 해시 테이블이 적합하지 않다.
😀 B - Tree만이 갖는 특징
- 각 노드 하나에 여러 데이터가 저장될 수 있으며, 각 노드 내 데이터는 항상 정렬된 상태다.
- 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가지며, 자식 노드 개수는 (n+1)다.
- 각 노드에는 여러 개의 key를 가지고 있고, 각 key에 대응하는 Data도 함께 갖고 있다.
✅ B - Tree가 선택된 이유
→ 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
→ 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
→ 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
참고
| https://velog.io/@sem/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4Index%EB%9E%80
'Database' 카테고리의 다른 글
| [DB] Transaction 트랜잭션 (0) | 2022.10.10 |
|---|---|
| [DB] 정규화 & 비정규화 (0) | 2022.10.07 |
| [DB] SQL vs NoSQL (4) | 2022.10.03 |
| [DB] SQL Injection (2) | 2022.09.30 |
| [DB] 조인(JOIN) 정리 (0) | 2022.09.28 |