[DB] 인덱스(Index)의 자료구조

인덱스의 자료구조는 해시(Hash) 테이블, B-Tree, B+Tree 등이 있다. 

1. 해시 테이블 

　　해시 테이블은 Key와 Value로 데이터를 저장하는 자료구조다. 

　　해시 테이블은 키, 해시함수, 해시, 값 저장소로 구성되어 있다. 키(Key)는 해시함수(Hash Function)를 통해 

　　해시(Hash)로 변경되고 해시(Hash)는 값(Value)와 매핑되어 저장소(Bucket)에 저장된다. 

　　키(Key)를 해시함수를 통해 해시로 만든 뒤 해시(Hash)를 주소로 삼아 데이터를 저장한다. 상품번호1 은

　　해시함수를 통해 해시값 ①이 생성된다. 상품번호2는 해시함수를 통해 해시 값 ②, 상품번호 3은 해시함수를

　　을 통한 해시 값③이 생성이 된다. 이 해시값을 인덱스로 삼아 Value를 빠르게 찾을 수 있다. 

 

• 키(Key) : 고유한 값으로 해시 함수의 Input이다. 임의의 길이를 가진 키는 공간 효율을 위해 해시함수를 통해 고정 길이를 가지고 있는 해시로 바꿔지게 된다. 
• 해시함수 : 키를 해시로 바꿔주는 역할을 한다. 같은 키를 해시함수를 사용하면 항상 같은 값의 해시를 받을 수 있다. 다른 키를 해시함수를 통해 해시로 변경했을 때 중복되서는 안된다. 그렇게 때문에 해시 충돌 가능성이 낮은 해시함수를 사용해야한다.
• 해시 : 키를 해시함수를 통해 연산한 결과를 해시라고 한다. 저장소에 값과 매칭되어 저장된다. 
• 값(Value) : 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 함께 저장된다.
• 저장소(Bucket) : 해시 테이블은 배열의 index를 생성하고 이를 활용하여 저장하고 검색한다. 실제 값이 저장되는 장소를 버킷이라고 한다. 

Hash 테이블 인덱스의 단점
- SELECT * FROM PRODUCT WHERE PRODUCT_ID = 1 일 때 시간복잡도는 O(1)이다. 
SELECT * FROM PRODUCT WHERE PRODUCT_ID > 1 일 때 해시 값은 정렬되어있지 않기 때문에 시간복잡도는
O(N)이다. 
- 특정 문자에서 일부분만 일치하는 데이터를 찾고싶을 때에는 사용 불가능
- 부등호 연산에는 적합하지 않음

2. B- Tree (Balance Tree)

　　자식 노드의 갯수가 이진 트리와는 달리2개 이상인 트리를 B-Tree라고 한다. 트리는 가장 상위에 있는 루트 노드,

　　중간에 있는 브랜치 노드, 마지막에 위치한 리프 노드로 구성된다. 노드의 데이터들은 항상 정렬된 상태이다.

3차 B-Tree 예시

• 노드의 데이터가 K개라면 자식 노드의 갯수는 K+1개다
• 노드의 데이터는 정렬된 상태이다
• 노드 데이터를 기준으로 왼쪽에는 노드 데이터보다 작은 값이, 오른쪽에는 큰 값이 저장된다
• 루트 노드는 리프 노드일 때를 제외하고 2개 이상의 자식 노드를 가져야 한다
• 모든 리프 노드는 같은 레벨에 있어야 한다

2.1 B-Tree의 검색 속도

배열에서 데이터를 검색할 때 시간복잡도는 O(N) 이 걸린다. 
B-Tree는 데이터를 검색할 때 시간복잡도는 트리의 높이만큼인 O(logN) 이 걸린다. 
검색뿐만아니라 삽입 삭제에서도 O(logN)이 걸린다.

1. 루트 노드부터 탐색을 시작한다.
2. 노드의 키를 순회해서 원하는 값이 존재하면 검색을 종료한다
3. 검색하려는 값이 존재하지 않으면 하위 노드를 검색한다.
4. 리프 노드까지 검색한다

3. B+Tree

　　B-Tree의 경우 모든 데이터를 순회하려면 모든 노드를 방문해야한다. B+Tree는 이를 개선시킨 자료구조이다.

　　B+Tree 자료구조에서는 리프 노드(leaf node)에 데이터를 저장하고 나머지 노드에서는 자식 포인터만 저장을

　　한다. 그리고 리프 노드는 서로 연결리스트 구조로 연결되어있다.