Database의 index
CS에 대해 하나하나 복습하면서 정리를 시작하고자 한다. 우선 첫 번째 내용으로는 데이터베이스의 인덱스 개념에 대해 공부해보았다.
1. index란?
인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조이다.
특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 인덱스가 생성된 후 쿼리문을 통해 인덱스에 접근할 수 있다.
- 아래 그림처럼 인덱스에 접근하면 먼저 인덱스에 저장되어 있는 데이터의 물리적 주소로 이동해 데이터를 가져오는 방식으로 동작하여 검색 속도를 향상 시킬 수 있다!!!!
인덱스는 책의 목차와 같은 역할을 하는데 동작 순서를 인덱스에서 원하는 데이터를 먼저 찾고 저장되어 있는 물리적 주소로 찾아간다고 생각하면 된다.
Index에 관한 내용은 자세히 알아두는 것이 좋습니다. 실제 DB 관련 작업을 할 때 대부분의 속도 저하는 바로 Select문 특히 조건 검색 Where절에서 발생하는데 가장 먼저 생각해 볼 수 있는 대안으로 Index를 생각할 수 있기도 하고, SQL 튜닝에서도 Index와 관련된 문제사항과 해결책이 많기 때문입니다.
2. index 장점
1) 조건 검색 효율성
테이블을 만들고 안에 데이터가 쌓이면 테이블의 레코드는 내부적으로 순서가 없이 저장된다. 이 경우 where절에 특정 조건에 맞는 데이터들을 찾아낼 때, 레코드의 처음부터 끝가지 다 읽어 조건을 비교해야되는데 이를 Full Table Scan이라고 한다.
인덱스 테이블의 경우 데이터들이 정렬되어 저장되어 잇기 때문에 해당 조건에 맞는 데이터들을 빠르게 찾아낼 수 있다.
2) 정렬 효율성
인덱스를 사용하면 order by에 의한 정렬과정을 피할 수 있다. order by는 부하가 많이 걸리는 작업인데 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리 보다 큰 작업이 필요하면 디스트 I/O도 추가적으로 발생한다.
인덱스를 사용할 경우 이미 정렬되어 있기 때문에 이러한 자원의 소모를 하지 않아도 된다.
3) MIN, MAX의 효율적인 처리
데이터가 미리 정렬되어 있기 때문에 MIN, MAX 값을 레코드 시작 값과 끝 값 하나씩만 가져오면 되므로 Full Table Scan을 할 필요가 없어 효율적이다.
3. index 단점
인덱스의 가장 큰 단점은 정렬된 상태를 계속 유지 시켜줘야 된다는 점이다. INSERT, UPDATE, DELETE를 통해 데이터가 추가되가나 값이 바뀌면 인덱스 테이블 내의 값들을 다시 정렬해야된다. 또한 인덱스 테이블, 원본 테이블 두 군데 모두 수정 작업을 해줘야 한다는 단점도 있다.
검색 시 인덱스가 무조건 좋은것은 아니다. 인덱스는 테이블의 전체 데이터 중에서 10%~15% 이하의 데이터를 처리하는 경우에만 효율적이고, 그 이상의 데이터를 처리할 때는 인덱스를 사용하지 않는 것이 더 좋다. 또한 인덱스 관리를 위해 데이터베이스의 약 10%에 해당되는 저장공간이 추가로 필요하다. 따라서 무조건 인덱스를 생성하는 것이 좋은것은 아니다!!!!
[ 인덱스(index)를 사용하면 좋은 경우 ]
규모가 작지 않은 테이블
INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
데이터의 중복도가 낮은 컬럼
기타 등등
4. index 관리
인덱스는 항상 최신의 데이터를 정렬된 상태로 유지해야한다. 따라서 INSERT, UPDATE, DELETE가 수행되면 계속 정렬을 해주어야 한다. 이 때 부하가 발생하는데 이를 최소화 하기 위해 인덱스는 DELETE에서 데이터를 삭제하지 않고 인덱스를 사용하지 않는다는 개념의 작업을 수행한다.
- INSERT: 새로운 데이터에 대한 인덱스를 추가합니다.
- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행합니다.
- UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가합니다.
5. index 생성 전략
인덱스는 특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 인덱스 테이블이 생성된다. 이러한 기준 컬럼은 최대한 중복되지 않는것이 좋다.(가장 좋은 것은 PK로 인덱스를 생성하는 것이다.) 아래의 기준이 기준 컬럼이 되기 좋은 컬럼이다.
- 조건절에 자주 등장하는 컬럼
- 항상 = 으로 비교되는 컬럼
- 중복되는 데이터가 최소한인 컬럼 (분포도가 좋은) 컬럼
- ORDER BY 절에서 자주 사용되는 컬럼
- 조인 조건으로 자주 사용되는 컬럼
6. 인덱스의 자료구조
인덱스에는 여러가지 유형이 존재한다. 이 절에서는 해시 테이블, B-Tree, B+Tree에 대해 설명한다.
1) 해시 테이블(Hash Table)
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
- 예를 들면 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.
2) B-Tree
B-Tree는 노드 하나에 여러 데이터가 저장될 수 있다.
각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. 그러므로 자식 노드 개수는 (n+1)을 가진다.
각 노드에는 여러 개의 Key를 가지고 있고 각 Key에 대응하는 Data도 함께 갖고 있다.
같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다. 이는 즉, 같은 노드 상에서 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다.
B-Tree 사용 이유
항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
3) B+Tree
B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 가지고 있다.
- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
- 리프노드들은 LinkedList로 연결되어 있다.
- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)
이러한 이유로 비록 B+Tree는 O(log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.
- InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.
데이터베이스의 인덱스였습니다~~
첫 CS 복습으로 데이터베이스의 인덱스에 대해 정리해 보았다. 물론 깊게 들어가면 더 많은 내용이 있겠지만 우선 간단히 중요한 내용을 정리했다. 더 정리할 내용이 생기면 추가할 생각이다. 다음 CS 공부로는 네트워크에 관련된 내용을 하면 좋을 것 같은데 생각해 봐야겠다!!!
📄 Reference
