index 란?
나는 그 동안 DB의 index를 사용하면서 index가 정확히 무엇을 해주는지 알지 못한채 사용해 왔다
이번에 우연히 이 index에 관해 잘 정리한 영상이 있어 해당 영상의 내용을 정리 해보고자 한다
만약 우리가 사전에서 단어를 찾아야 한다고 상정해보자 일반적으로 사전은 알파벳순으로 단어가 정리되어 있고 또한 단어를 쉽게 찾아 볼 수 있는 색인또한 존재한다
그러나 우리가 단어를 찾을때 정렬도 색인도 존재 하지않는다면 어떻게 단어를 찾아야 할까
첫번째 단어부터 마지막 단어까지 찾는 단어가 나올때까지 하나씩 찾아볼 수 밖에 없는 비극이 생기게 된다
DB도 이와 똑같다 DB에서 우리가 검색을 하게 되면 테이블 모두를 찾게 되는데 행의 개수가 100개, 1000개 라면 문제가 없지만 만약 십만을 넘고 백만을 넘어선다면 검색의 속도가 굉장히 느려질 수 밖에 없다
이러한 문제를 해결하기 위해 존재하는게 DB의 index 이다
데이터를 빠르게 찾기위해서는 정렬을 해야하는데 컬럼을 기준으로 정렬된 복사된 컬럼을 index라고 한다
이 정렬된 테이블이 1~100의 값을 가진다면 원하는 값을 찾기 위해서는 50보다 큰지 75보다 작은지 등을 이용해 반씩 잘라가며 찾아가면 된다
이 테이블은 단순히 배열이나 리스트 처럼 정렬된게 아닌 트리구조를 가진채 졍렬된다
사용되는 트리구조는 여러가지가 있다
이진 탐색 트리 (Binary Search Tree)
이진 트리는 다음과 같은 특성을 가진다
중복된 키값을 허용 하지 않는다부모 노드의 왼쪽에는 작은 키값 오른쪽에는 큰값이 들어간다하위 트리도 이진 트리여야 한다50, 15, 62, 70, 7, 54, 11 순으로 값이 들어온다면
해당 모양의 트리가 생기게 된다
이 트리에서 54를 찾고자 한다면 단 2번의 노드만 거치면 원하는 값을 얻을 수가 있다
B-Tree
자식 노드가 2개 이상인 트리
또한 노드내의 데이터가 n개 까지 들어간다 이경우 n차 b-tree 라고 한다
특성
노드의 데이터 개수가 n개라면 자식 노드는 n+1개이다노드의 데이터는 반드시 정렬된 상태부모노드의 자식노드 데이터들은 부모노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰값들은 오른쪽 서브 트리에 이루어 져야 합니다.키값은 중복을 허용하지 않는다root node가 아닌 노드들은 적어도 M/2개의 자식 노드를 가지고 있습니다. (최대 M개)검색 과정은 이진트리와 비슷하다 한노드에 데이터가 많을 뿐이라고 생각하면 된다
B+Tree
B-tree와 대조적으로 B+tree는 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.
b+tree는 말단 노드에 모든 데이터가 몰려있고 말단 노드를 제외한 나머지는 빠른 접근을 위한
인덱스 역할만을 하기에 인덱스 조합이라 부른다
또한 말단 노드는 연결 리스트로 되어있기에 1~5의 값을 가져오는 등의 범위값을 가져오는데 유리하다
