칼럼의 값과 해당 레코드가 저장된 주소를 Key-Value 쌍의 인덱스로 만들어두어 해당 테이블에 대한 탐색을 빠르게 해주는 자료 구조이다.
Index는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 것은 빠르지만 새로운 값의 추가, 삭제, 수정이 발생할 경우에는 성능을 오히려 저하시킬 수 있다.
인덱스는 크게 2가지 자료구조를 채택하고 있다.
일반적으로 인덱스에 사용되는 자료구조이다. 칼럼의 값을 변형하지 않고, 원래의 값을 이용해 트리구조에 저장하여 인덱싱하는 알고리즘이다.
MySQL의 DB engine인 InnoDB는 B+tree로 이루어져 있으며 이는 B-Tree의 확장된 개념이다.
시간복잡도: O(logN)
어떤 값에 대해서도 같은 시간(O(logN))에 결과를 얻을 수 있다.
B-Tree는 이진트리와 유사하지만 하나의 노드당 2개 이상의 자식노드를 허용한다. B-Tree는 균형트리이며 이는 루트로부터 리프까지의 거리가 일정한 트리 구조임을 의미한다.
장점으로는 ‘균일성’을 꼽을 수 있는데 이는 ‘어떤 값에 대해서도 같은 시간(O(logN))에 결과를 얻을 수 있다’는 것을 의미한다. 따라서 데이터 양이 커질 수록 성능이 향상된다.
B+Tree는 B-Tree의 확장 개념으로, B-Tree의 경우 internal 또는 branch 노드에 key와 data를 담을 수 있다. 하지만 B+tree의 경우 브랜치 노드에 key만 담아두고 data를 담지 않는다. 오직 leaf node에만 key와 data를 저장하고 리프 노드끼리 Linked List로 이루어져 있다.
이를 통해 얻을 수 있는 장점은 다음과 같다.
- 메모리 성능 확보 - 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
- select * 성능 향상 - 해당 테이블의 모든 데이터를 조회할 때, b-tree의 경우 모든 노드를 조회해야 하지만 b+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색으로 모든 데이터를 조회할 수 있다.
- 구간 탐색 성능 향상 - Link List로 이루어져 있기 때문에 최소값만 찾으면 다음 좌표들로 이동하며 탐색할 수 있다.
시간복잡도: O(1) ~ O(N)
보편적으로는 해시함수에 의해 고유 index를 가지게 되어 O(1)의 시간복잡도를 가지지만 Hash값 충돌이 발생할 경우 이후 연결된 리스트들 까지 검색해야 하므로 최대 O(N)까지 증가할 수 있다.
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조. Key값을 해시 함수를 통과시켜 얻은 값(고유 인덱스)을 인덱스로 데이터를 저장하기 때문에 O(1)의 시간복잡도를 가진다.
예를 들어 John Smith를 저장 할 때, bucket[h("John Smith")]
과 같이 Key값을 Hash함수를 통과 시킨뒤 바로 bucket의 인덱스로 사용한다.
따라서 해시 테이블을 사용하여 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수 수행 한번으로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다.하지만 값을 변형해서 인덱싱 하므로 값의 일부만으로 검색하고자 할 때, 해시 인덱스를 하용할 수 없다.
hash table의 경우 단일 데이터에 접근할 때의 시간복잡도가 O(1)이고 b+-tree의 경우 O(logN)의 시간 복잡도를 가진다. 하지만 hash table의 경우 부등호 연산(<>)이 포함되어 있을 경우 모든 데이터를 순회해야 하여 O(N)의 시간복잡도를 가지는 반면 b+-tree의 경우 똑같이 O(logN)의 시간복잡도를 가지기 때문에 일반적으로 데이터베이스에서는 b+-tree를 인덱스의 자료구조로 사용한다.
두개 이상의 Atrribute를 합쳐서 index로 설정하는 것을 의미한다. (attribute1, attribute2)를 Composite Index로 설정하였을 때, attribute1으로 정렬후 동일 attribute1에 대해서 attribute2로 정렬한다. 따라서 attribute1로 조회 시에는 성능이 좋아지지만 attribute2로만 조회 시에는 index 성능이 좋지 않다.
https://zorba91.tistory.com/293
https://bcho.tistory.com/1072
https://mangkyu.tistory.com/102