인덱스의 핵심은 탐색범위를 최소화 하는 것
HashMap
-
키와 값이 있어 단건 검색 속도는 O(1)
-
범위 탐색은 O(N)
-
like 'AB'% 같은 검색은 키를 하나씩 꺼내서 비교해야 하기 때문에 사실상 불가
List
-
정렬되지 않은 리스트 탐색은 O(N) (어디서부터 탐색해야 할지 모름)
-
정렬된 리스트의 탐색은 O(logN)
-
정렬되지 않은 리스트의 정렬 시간 복잡도는 O(N) ~ O(N * logN)
-
삽입 / 삭제 비용이 매우 높다.
Tree
-
트리 높이에 따라 시간 복잡도가 결정된다.
-
트리 높이를 최소화 해야 한다.
-
한쪽으로 노드가 치우치지 않도록 균형잡힌 트리를 사용해야 한다.
B + Tree
-
삽입 / 삭제시 균형을 이룸
-
하나의 노드가 여러 자식들을 가질 수 있어 트리 높이 최적화에 유리하다.
-
리프 노드에만 데이터가 존재하여 연속 데이터 접근에 유리하고 검색시 리프 노드만 훑어 보면 된다.
