TIL | 2.24.금 [인덱스 | B-Tree/Hash Table]

인덱스

[인덱스 관련 참고 자료]

https://wonprogrammer.tistory.com/143

TIL | 1.17.화 [CS 기초지식 | Index]

 

 

---

 

인덱스의 자료구조

 

B-Tree (Balanced - Tree) 란?

B-트리는 모든 노드가 여러 키를 포함하고 2개 이상의 자식을 갖는 자체 균형 탐색 트리입니다.

 

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 또한 가장 먼저 도입된 알고리즘임에도 불구하고 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다.

여기서 나아가 B-Tree에서 여러 가지 변형된 형태의 알고리즘인 B+-Tree 또는 B*-Tree 또한 자주 사용됩니다.

 

B-Tree는 컬럼의 원래 값을 변형시키지 않고 (물론 값의 앞부분만 잘라서 관리하기는 하지만) 인덱스 구조체 내에서는 항상 정렬된 상태로 유지하고 있습니다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 일반적인 용도에 적합한 알고리즘이다.

 

(추가로 B-Tree의 "B"는 "Binary(이진)"의 약자가 아니라 "Balanced"를 의미합니다.)

 

 

여기서, 위 그림을 참고해 B-Tree를 살펴보자면

B-Tree는 트리 구조의 최상위에 하나의 "루트 노드"가 존재하고 그 하위에 자식 노드가 붙어 있는 형태이다. 트리 구조의 가장 하위에 있는 노드를 "리프 노드"라 하고, 트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간 노드를 "브랜치 노드"라고 한다. 

 

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있는 특징이 있다.

 

 

 

[B-Tree 참고 링크]

https://12bme.tistory.com/138

[Real MySQL] B-Tree 인덱스

 

 

---

 

Hash Table 이란?

해시 테이블은 데이터 요소의 주소/인덱스 값이 해시 함수에서 생성되는 데이터 구조 유형이다. 인덱스 값이 데이터 값에 대한 키로 동작하므로 매우 빠른 데이터 액세스가 가능하다.

즉, 해시 테이블은 키-값 쌍을 저장하지만 키는 해싱 함수를 통해 생성됩니다. 따라서 키 값 자체가 데이터를 저장하는 배열의 인덱스가 되기 때문에 데이터 요소의 검색 및 삽입 기능이 훨씬 빨라진다. 조회하는 동안 키가 해시되고 결과 해시는 해당 값이 저장된 위치를 나타내게된다.

 

 

Hash Table의 개념은 버킷 배열에 항목(키/값 쌍)을 배포하는 것입니다. 

→ 키가 주어지면 알고리즘은 항목을 찾을 수 있는 위치를 제안하는 인덱스를 계산한다. 해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다. 

 

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하기 때문에

 

따라서 위와같은 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다.

 

 

 

[해시 테이블 참고 자료]

https://wonprogrammer.tistory.com/140

TIL | 1.5.목 [CS 기초지식 | 해시 테이블]

 

 

---

 

 

[참고자료]

https://applepick.tistory.com/155

[index] B+-Tree, Hash Table