티스토리 뷰
전반적인 개념을 알 수 있는 영상이다.
index?
index란, 추가적인 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조이다.
특정 컬럼에 index를 생성하게 되면 해당 칼럼의 데이터들을 오름차순으로 정렬하여 저장한다.
index를 쓰는 이유
위에서 언급했듯이 index는 추가적인 저장공간을 필요로 하고,
DB가 하나 더 생기는 것과 마찬가지이므로 관리를 해줘야 하며
굳이 필요하지 않은 상황에 쓰게 된다면 오히려 성능이 저하될 수도 있는 단점들을 갖고 있다.
(원본 테이블에서 데이터의 삽입, 수정, 삭제가 이루어진다면 인덱스도 수정되어야 하므로
수정이 자주 이루어지는 테이블보다는 검색이 자주 사용되는 테이블에서 사용하며
값의 분산도가 높은 칼럼에 만든다. → 성별보다는 주민번호)
그럼에도 index를 쓰는 이유가 무엇일까?
테이블의
아무런 설정이 되어있지 않은 칼럼에서(기본키와 같은 칼럼은 자동으로 정렬되므로 제외한다는 것)
특정 데이터를 찾는다고 가정하면 기본적으로 처음부터 끝까지의 모든 데이터를 조회해서 찾아낸다.
이를 풀 스캔(Full Scan)이라고 하는데,
만약 1억 개의 데이터가 포함되어 있고 찾는 데이터가 9999만 번째에 있다면 그 데이터를 찾기 위해
처음부터 조회를 하게 될 것이고 이는 효율적인 면에서 매우 불리해진다.
하지만 index는
데이터들이 정렬되어 저장되어 있기 때문에
풀 스캔이 아닌 레인지 스캔(Range Scan)으로 데이터를 찾을 수 있고
원하는 데이터를 빠르게 찾아낼 수 있게 된다.
index 구조
B-tree, B*tree
그림처럼 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수도 있다.
노드에 여러 데이터가 들어있어도 그 또한 정렬되어 있고 중복되지 않는다.
→ 이진트리보다 훨씬 많은 데이터를 더 효율적으로 저장할 수 있다.
B-tree는 균형이진트리(leaf node들의 레벨차이가 최대 1 레벨까지만 나는 트리로,
균형이 깨지면 별도 로직을 통해 다시 균형을 유지)의 연속이므로 균형을 유지하며
최악의 경우라도 O(logN)의 검색 성능을 보여준다.
하지만 이런 특성 때문에 구조를 유지하기 위해 계속해서 추가적인 연산이 수행되거나 새로운 노드가 생성되는데,
이를 최소화하기 위해 B*tree가 등장했다.
B-tree와 B*tree의 대표적인 차이점은
기존 노드의 자식 노드 수 최소 제약 조건이 조금 해소되고
노드가 가득 차게 된다면 분열 대신 이웃한 형제노드로 재배치하게 된다. (더 이상 재배치할 수 없을 때 분열)
B+tree
B+tree는 같은 레벨의 모든 키 값들이 정렬되어 있고, 같은 레벨의 형제 노드는 연결리스트 형태로 이어져 있어,
특정 값을 찾는다고 했을 때 leaf node에 모든 자료들이 존재하고 연결되어 있으므로 탐색에 있어 매우 유리하다.
그렇다면 B-tree와의 뚜렷한 차이점은 무엇일까?
B-tree는 리프 노드가 아닌 각자 key마다 data를 가진다면,
B+tree는 리프 노드에 모든 key, data를 가진다.
B-tree는 옆에 있는 리프 노드를 검사하기 위해서는 다시 루트 노드부터 검사해야 하지만,
B+tree는 리프 노드에서 선형검사를 수행할 수 있어 시간복잡도를 줄일 수 있다.
B+tree의 리프 노드의 부모 key는 리프 노드의 첫 번째 key보다 작거나 같다.
리프 노드의 key들을 트리가 가지고 있는 경우인 B+tree는
data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다.
참고 자료
https://choicode.tistory.com/27
https://ssocoit.tistory.com/217
'CS' 카테고리의 다른 글
| 대규모 트래픽 처리 (2) (0) | 2023.03.07 |
|---|---|
| 대규모 트래픽 처리 (1) (0) | 2023.03.01 |
| CPU-프로세스와 스레드 (0) | 2023.02.07 |