인덱스와 자료구조

1. 인덱스란 정렬된 자료구조이다
 EX: A테이블의 a라는 컬럼에 인덱스를 생성하면
     a를 pk로 하고, 그 데이터가 있는 주소가 담긴 컬럼으로 구성된 인덱스 테이블이 만들어짐 / 그리고 a는 정렬되어있다.
     따라서 A테이블의 가장 작은 a를 구하려고 하면 인덱스 테이블의 맨 위 데이터 1개만 보면 되므로 빠르다.
       > 즉, 인덱스의 핵심은 탐색(검색) 범위를 최소화 하는 것

2. 인덱스와 자료구조
 - HashMap : 단건 검색 속도 O(1)
 - 그러나 범위 탐색은 O(N) > 범위 내에 데이터를 하나하나 다 꺼내봐야 함
 - 전방 일치 탐색 불가 ex) like 'AB%' > 하나하나 다 꺼내봐야 함

 - List : 정렬되지 않은 리스트 탐색은 O(N)
 - 정렬된 리스트의 탐색은 O(logN)
 - 정렬되지 않은 리스트의 정렬 시간 복잡도는 O(N) ~ O(N*logN)
 - 삽입 / 삭제 비용이 매우 높음 : 가운데 값을 지우면 오른쪽 값들은 왼쪽으로 다 옮겨야 함

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

 - B+Tree : 삽입 / 삭제시 항상 균형을 이룸
 - 하나의 노드가 여러 개의 자식노드를 가질 수 있음
 - 리프노드에만 데이터 존재
     > 연속적인 데이터 접근시 유리하다.
 - 따라서 인덱스로 많이 활용되는 알고리즘이다.