index

정의; DB에서 index란?

추가적인 쓰기 작업과 저장 공간을 활용해 데이터베이스 테이블의 특정 열(데이터)에 대한 검색 속도를 향상시키기 위해 사용되는 데이터 구조

사용 목적

왜?

정의에 나온 것처럼 자주 찾는 데이터의 검색 속도를 향상시키기 위함이다.

언제?

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않은 컬럼
• JOIN, WHERE 또는 ORDER BY 에 자주 사용되는 컬럼
• 기본적으로 B 트리로 구현되어있어 정렬되어있다는 전제 하에 이루어지는 이야기
  • 범위 검색이 필요할 때
  • 정렬이 필요할 때

장단점

장점

• 인덱스에 기록된 데이터에 대한 검색 속도가 향상한다.
• 동일하게 조회를 사용하는 UPDATE, DELETE의 성능이 향상된다.

단점

• 일정 공간, 일반적으로 DB의 약 10%에 해당하는 공간을 사용해야한다.
  따라서 색인해놓는 데이터가 많아질 수록 인덱스 테이블 크기가 커진다.
• 검색(조회) 기능에서는 성능 향상을 보일 수 있으나 그 외 삽입, 수정, 삭제 시에 인덱스도 함께 업데이트되어야 하므로 자주 일어난다면 속도가 감소할 수 있다.

구현 알고리즘

Hash table

해시 테이블 기반으로 인덱스는 {해싱된 컬럼의 값, 데이터 위치} 값을 가진다.
시간복잡도는 O(1)로 빠른 검색을 지원한다.

하지만 인풋값이 1이라도 달라지는 순간 아예 다른 아웃풋을 내는 해시 함수의 특성상, 부등호 연산에는 적합하지 않다.

그래서 일반적으로 아래와 같은 알고리즘이 사용된다.

B tree

이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조
DB와 파일 시스템에서 자주 사용된다.

 

특징

• 루트에서 리프까지의 거리가 모두 일정하다.
• 하나의 노드에 많은 수의 정보를 가질 수 있다.
• 노드는 최대 M개의 자식 노드를 가질 수 있다고 하면, 해당 트리는 M차 B 트리라고 한다.
• M차 B 트리라고 할 때, 노드 당 키는 최대 M-1개 가질 수 있다.
• 각 노드는 최소 M/2 개의 자식 노드를 가진다. (루트와 Leaf 노드 제외)
• 각 노드는 최소 M/2 - 1 개의 key를 가진다. (루트와 Leaf 노드 제외)
• 항상 Leaf 노드에 데이터가 추가된다.
• 노드가 넘치면 가운데 Key를 기준으로 좌우 Key를 분할해 가운데 Key는 승진한다.
    노드가 넘친다: 3에서 봤던 특징처럼 하나의 노드 당 최대 key 수가 정해져있는데, 이를 넘었을 때 노드가 넘친다고 한다.

B+ tree

B 트리의 변형된 형태로, leaf 노드에만 값(데이터)이 저장이 되고 그 윗 노드들은 키와 포인터로만 구성되어 인덱스 역할을 수행한다.
모든 노드가 같은 레벨에 대해 정렬된 키값을 가지고 있다.

 

연결 리스트
B 트리 때 탐색을 위해 노드를 찾아서 이동해야한다는 단점을 보완하기 위해 leaf 노드들은 연결리스트 형태이다.
덕분에 옆에 있는 리프 노드를 다시 검색해야할 때 리프노드에서 선형 검사를 할 수 있다.
** 선형 검사: 데이터 집합에서 특정 값을 찾기 위해 처음부터 순차적으로 검색하는 방법

• 장점
  • 루트부터 모든 리프 노드까지의 깊이가 같아서 O(log N)의 시간복잡도를 가진다.
  • 데이터가 정렬된 상태로 리프 노드에 연결 리스트 구조로 저장되어있어 데이터를 재검색할 때 모든 노드를 다시 다 돌지 않아도 된다.
  • 리프 노드가 연결 리스트로 구성되어있어, 선형 탐색을 지원한다.
• 단점
  • 값(데이터)은 리프 노드에 저장하고, 그 외의 노드는 데이터의 인덱스로 사용하니 값이 많아질수록 메모리 사용량이 높아질 수 있다.

결론

요즘 사용되는 DB 인덱스는 일반적으로 B+ 트리로 구현되어있다.
그래서 B+ 트리의 특징, 장단점을 DB 인덱스가 비슷하게 가져갈 수 있다.
예를 들면, 빠른 검색 지원, 데이터를 정렬된 상태로 유지하며 범위 탐색 지원 등

 

출처

---

https://mangkyu.tistory.com/96
https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC
https://nooblette.tistory.com/entry/B-%ED%8A%B8%EB%A6%ACB-Tree
https://velog.io/@kyeun95/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-B-Tree%EB%9E%80