- 인덱스: 기준에 의해 정렬한 칼럼
- 인덱스가 되기 위해 필요한 조건: 기준에 의한 정렬
- 인덱스 자료구조: B 트리
- 인덱스는 B 트리 형태로 저장되서 검색 시 lower, between, upper 로 분할해 search 가 가능하다
- 인덱스 최종 자료구조: B+ 트리
- 데이터는 leaf에 저장 된다.
- 데이터들은 서로 값이 인접한 데이터끼리 link 되어있다
- node는 search guideline 만 제공한다.
- B+ 트리 특징: 데이터들 끼리 연결되어 있어 범위 검색 (range search) 이 쉬워진다
- 시간 복잡도:
- 검색: 트리를 타면서 검색 O(log N)
- 수정:
- 단순 수정 시: 검색에 드는 비용 O(log N)
- 삭제 및 생성 시 : O(log N) + O(log N) = O(log N)
- 삽입:
- 유효 노드를 찾음 O(log N). 유효 노드에 키가 하나 추가 됨 O(1). 링크드리스트에 데이터가 추가됨 O(1).
- 분할: 노드가 가득차서 새로운 노드를 만들고 이에 따라 부모 노드의 수정이 필요함. B+ 트리는 균형을 유지해야함.
- 삭제:
- 유효 노드를 찾음 O(log N). 유효 노드에서 키가 하나 삭제 됨 O(1). 링크드리스트에서 데이터가 삭제됨 O(1).
- 병합: 키가 삭제 되면서 노드의 key가 최소 갯수 이하로 줄어들어 형제 노드의 key를 빌려와야 하거나 노드를 지우고 부모 노드의 수정이 필요함. B+ 트리는 균형을 유지해야함.
- B 트리와 B+ 트리 차이점 정리
- 노드 차이점 (데이터): B+ 트리에는 데이터가 없다. 그래서 실제 데이터는 리프까지 가야만 얻을 수 있다.
- 노드 차이점 (검색):
- B 트리 - 기존에 검색 시 자식들 기준으로 찾는 값이 가장 작은 자식보다 작은, 가장 큰 자식보다 큰지, 값이 자식 A와 자식 B 사이인지 를 확인
- B+ 트리 - 자식의 값은 key로 갖고 있다고 생각하면 됨. Child 가 n 이라면, key는 n-1 개 있음 (예: 가는 방향마다 child가 있고, 가는 방향은 key A보다 작을 때, key B보다 클 때, key A와 key B 사이일 때, 이렇게 있으니 key는 2개, child는 3개가 된다).
- 인덱스 저장 위치:
- clustered: 테이블 자체가 인덱싱 기준으로 저장됨 (예: ID)
- non-clustered: 인덱스 자체가 따로 저장됨
- 예) B+ 트리 구조로 저장되고 각 node는 index 값과 실제 데이터의 row pointer 를 갖음
- 인덱스 단점:
- 용량: 테이블에 row가 하나 더 늘어나는 것이라 생각해도 됨
- 시간:
- 삽입, 수정, 삭제 시 index에도 반영이 되어야함.
- index의 삽입, 수정 삭제가 발생함
'DB' 카테고리의 다른 글
DB 면접 예상 질문) "다음 상황 별 SQL 쿼리를 작성해주세요." (0) | 2025.02.27 |
---|---|
DB 면접 예상 질문) "제1,2,3정규화에 대해 설명해주세요." (0) | 2025.02.27 |
DB 예상 면접 질문) "ACID가 뭐에요? 어디에 쓰여요?" (0) | 2025.02.27 |