DB 인덱스
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 기술이다. 인덱스는 테이블 내 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.
인덱스 사용 시 장단점
장점
- 검색은 속도가 무척 빨라질 수 있다. (단, 항상 그런 것은 아니다.)
- 그 결과 해당 쿼리의 부하가 줄어들어서 결국 시스템 전체의 성능이 향상된다.
단점
- 인덱스가 데이터베이스 공간을 차지해서 추가적인 공간이 필요해지는데, 대략 그 비율은 10% 정도이다.
- 처음 인덱스를 생성하는 데 시간이 많이 소요될 수 있다.
- 데이터의 변경 작업이 자주 일어날 경우에는 오히려 성능이 나빠질 수 있다.
인덱스 자료구조
Hash Table
해시 테이블은 Key-Value로 이루어진 데이터를 저장하는데 특화된 자료 구조이다. 해시 테이블 기반의 DB Index는 특정 컬럼의 값과 데이터의 위치를 Key-Value로 사용한다.
해시 테이블은 내부에 버켓이라고 하는 배열이 존재한다. 해시 함수를 통해 Key를 고유한 해시 값으로 변환시키는데, 이를 버켓 배열의 인덱스로 사용하며 해당 인덱스에 Value를 저장한다. Key 값으로 Value가 저장되어 있는 위치(주소)를 바로 산출할 수 있기 때문에, 해시 테이블의 평균적인 시간 복잡도는 O(1) 이다. 하지만 해시 함수를 제대로 정의하지 않으면 해시 함수를 통해 산출한 해시 값이 중복되는 해시 충돌이 발생한다. 너무 많은 해시 충돌이 발생하면 검색 성능이 하락해 시간 복잡도가 O(N)에 수렴할 수 있다.
Index 자료 구조로 해시 테이블을 사용하는 경우는 매우 제한적이다. 해시 함수는 Key가 조금이라도 다르면 완전히 다른 해시 값을 생성한다. 이러한 해시 테이블을 사용하는 Index의 경우 WHERE 조건의 등호(=) 연산에는 효율이 좋지만, 부등호 연산(>, <)은 부적합하다. 해시 테이블은 내부 데이터들이 정렬되어 있지 않아 탐색이 효율적이지 않다.
B-Tree
B-Tree란 자식 노드가 2개 이상인 트리를 의미한다. 이진검색 트리처럼 각 Key의 왼쪽 자식은 항상 Key보다 작은 값을, 오른쪽 자식은 큰 값을 가진다. B-Tree 기반의 DB Index는 특정 컬럼의 값(Key)에 해당하는 노드에 데이터의 위치(Value)를 저장한다.
각 Node에는 여러개의 Key를 갖고 있고 각 Key에 대응하는 Data도 함께 갖고 있다. Key는 Binary Search와 유사한 형태로 정렬되어 각 Node에 배치된다. Binary Search에서 오른쪽 Child Node의 Key는 자신보다 작고 왼쪽 Child Node의 Key는 자신보다 큰데, B-Tree에서도 각 Key에 대해서 유사한 규칙이 적용된다.
B-Tree의 Key-Value 값들은 항상 Key를 기준으로 오름차순 정렬이다. 이로 인해 부등호 연산(>, <)에 대해 해시 테이블보다 효율적인 데이터 탐색이 가능하다. 또한 B-Tree는 균형 트리(Balanced Tree)로서, **최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일하기 때문에 평균 시간 복잡도는 O(logN)**이다.
하나의 Node에 여러개의 Key를 갖는 특성 때문에 용량이 큰 Block 단위로 Data를 Read/Write하는 Disk 환경에서는 Binary Search Tree보다 B-Tree를 이용하는 것이 유리하다.
B+Tree
B+ Tree는 B-Tree를 개량한 자료구조 이다. B-tree처럼 모든 Leaf Node는 동일한 Depth를 갖는다. B-Tree와의 가장 큰 차이점은 Inner Node에는 Key만 저장이 되고 Leaf Node에 Key와 Data를 함께 저장한다는 점이다. Leaf Node에만 Data가 저장되기 때문에 Leaf Node 사이를 Link (Pointer)로 연결하여 B-Tree에 비하여 쉬운 순회가 가능하도록 만든점도 B+ Tree의 특징이다.
DB Index 컬럼은 부등호(>, <)를 이용한 순차 검색 연산이 자주 발생한다. B-Tree가 해시 테이블보다 부등호를 이용한 검색 연산 성능이 좋지만, 순차 검색의 경우 중위 순회를 하기 때문에 효율이 좋지 않다. 따라서 MySQL 엔진인 InnoDB는 B-Tree를 확장 및 개선한 B+Tree를 Index의 자료 구조로 사용한다.
B+Tree에서 말단의 리프 노드들끼리는 LinkedList 구조로 서로를 참조하고 있다. 따라서 부등호(>, <)를 이용한 순차 검색 연산을 하는 경우, 많은 노드를 방문해야 하는 B-Tree에 비해 B+Tree는 말단 리프 노드를 저장한 LinkedList를 한 번만 탐색하는 등 속도 이점이 있다.
B+ Tree의 Inner Node는 Data가 없기 때문에 B-Tree의 Inner Node에 비하여 용량작다. 하나의 Disk Block에 더 많은 Inner Node를 배치 할 수 있게 되어, Key 탐색시 B-Tree에 비하여 상대적으로 적은 Disk Block만 읽어도 된다. 이러한 이점 때문에 일반적으로 B+ Tree는 Key 탐색시 B-Tree보다 좀더 나은 성능을 보여준다.
인덱스의 종류
클러스터형 인덱스(Clustered Index)
- 영어 사전처럼 책의 내용 자체가 순서대로 정렬되어 있어서 인덱스 자체가 책의 내용과 같은 것
- 테이블 당 한 개만 생성할 수 있다. 그러므로 어느 열에 클러스터형 인덱스를 생성하는지에 따라서 시스템의 성능이 달라질 수 있다.
- 생성 시에는 데이터 페이지 전체가 다시 정렬된다. 그러므로 이미 대용량의 데이터가 입력된 상태라면 신중하게 생각해야 한다.
- 보조 인덱스보다 검색 속도는 더 빠르다. 하지만 데이터의 입력/수정/삭제는 더 느리다.
보조 인덱스(Secondary Index)
- <찾아보기>가 별도로 있고, <찾아보기>를 찾은 후에 그 옆에 표시된 페이지로 가야 실제 찾는 내용이 있는 것
- 데이터 페이지는 그냥 둔 상태에서 별도의 페이지에 인덱스를 구성한다.
- 인덱스 자체의 리프 페이지는 데이터가 아니라 데이터가 위치하는 주소값이다. 클러스터형 인덱스보다 검색 속도는 더 느리지만 입력/수정/삭제는 덜 느리다.
- 테이블 당 여러 개를 생성할 수 있다. 하지만 남용할 경우에는 오히려 시스템 성능을 떨어뜨리는 결과를 초래할 수 있으므로 꼭 필요한 열에만 생성하는 것이 좋다.
MYSQL 인덱스의 특징
- PRIMARY KEY로 지정한 열은 클러스터형 인덱스가 생성된다.
- UNIQUE NOT NULL로 지정한 열은 클러스터형 인덱스가 생성된다.
- UNIQUE(또는 UNIQUE NULL)로 지정한 열은 보조 인덱스가 생성된다.
- PRIMARY KEY와 UNIQUE NOT NULL이 있으면 PRIMARY KEY로 지정한 열에 우선 클러스터형 인덱스가 생성된다.
- PRIMARY KEY로 지정한 열로 데이터가 오름차순 정렬된다.
인덱스를 생성할 때 고려할 점
- 테이블 조회 시에 WHERE 절의 조건에 해당 열이 나오는 경우에만 인덱스를 사용한다.
- WHERE절에 사용되더라도 자주 사용해야 가치가 있다.
- 데이터의 중복도가 높은 열은 인덱스를 만들어도 별 효과가 없다.
- 외래 키를 지정한 열에는 자동으로 외래 키 인데스가 생성된다.
- JOIN에 자주 사용되는 열에는 인덱스를 생성해 주는 것이 좋다.
- 사용하지 않는 인덱스는 제거하자.
참고
https://www.youtube.com/watch?v=iCIK7qv6GnU