조회 최적화를 위한 인덱스 이해하기 - 03. 인덱스 자료구조

인덱스의 핵심 : 탐색(검색) 범위를 최소화 하는 것

검색이 빠른 자료구조들은 어떤 것이 있을까?

• Hash Map, List, Binary Search Tree

Hash Map

• 단건 검색 속도 O(1)
• 그러나 범위 탐색은 O(N)
• 전방 일치 탐색 불가 ex) like ‘AB%’ → hash map은 꺼내서 일일이 다 비교해보아야 함

List

• 졍렬되지 않은 리스트의 탐색은 O(N)
• 정렬된 리스트의 탐색은 O(logN)
• 정렬되지 않은 리스트의 정렬 시간 복잡도는 O(N) ~ O(N*logN)
• 삽입 / 삭제 비용이 매우 높음 → 중간 값을 삭제하기 위해서는 뒤에 있는 것을 모두 옮겨야 함

Tree

• 트리 높이에 따라 시간 복잡도가 결정됨
• 트리의 높이를 최소화하는 것이 중요!
• 한쪽으로 노드가 치우치지 않도록 균형을 잡아주는 트리 사용 (ex. Red-Black Tree, B+Tree)

B+ Tree

• 많이 사용하는 Tree
• 삽입 / 삭제시 항상 균형을 이룸
• 하나의 노드가 여러 개의 자식 노드를 가질 수 있음 → 중요한 장점
• 리프노드(마지막 노드)에만 데이터 존재(나머지 노드들은 데이터를 찾아가기 위한 키) → 연속적인 데이터 접근 시 유리

예제

MySQL에서는 PK 설정이 굉장히 중요하다 → PK 사이즈가 커지게 되면, 하나의 노드가 가질 수 있는 데이터의 수가 적어진다.

• 담을 수 있는 노드의 수가 적어진다면 리밸런싱(삽입이나 삭제 되었을 때의 tree 모양이 바뀌는 것)이 꽤 빈번하게 발생할 수 있음 ‘
• 인덱스를 사용한다는 것은 조회의 성능을 높일 수 있지만, 쓰기나 갱신의 성능을 낮춘다.

---

2023 KAKAO Tech Campus_BackEnd 필수 과정
DB(MySQL) 강의 정리 내용입니다.