B-Tree?
- 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조.
- 노드 내의 데이터가 1개 이상일 수 있으며 노드 내 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree라고 한다.
- 부모 노드 데이터를 기준으로 작은 값들은 왼쪽 서브 트리에, 큰 값들은 오른쪽 서브 트리에 저장한다.
- Leaf 노드의 레벨은 모두 같아야 한다.
- 탐색에 O(logN)의 시간 복잡도를 가진다.
- 같은 노드의 데이터들은 실제 메모리 상에 차례대로 저장되어 있다.
- 데이터 접근시 인덱스로 접근 가능하다.
Hash Table?
- 해싱을 사용하여 데이터를 저장하는 자료구조
- 해싱: 임의의 길이의 값을 해시 함수를 활용하여 고정된 크기의 값으로 변환하는 과정 - 해싱한 값이 인덱스이며 (Key, Value)로 데이터를 저장한다.
- 탐색에 O(1)의 시간 복잡도를 가진다. (해쉬 충돌이 없을 경우)
- 해쉬 충돌이 난 경우 해당 탐색시 해당 키에 연결된 모든 요소들을 탐색하는 과정이 필요하다.
Index?
DB내의 데이터 검색을 빠르게 하기 위해 다양한 자료구조를 활용하여 순서대로 정리하는 과정이다.
index가 없다면 원하는 데이터를 찾기 위해 컬렉션 내부의 도큐먼트들을 스캔해야 된다.
MongoDB?
MongoDB indexes use a B-tree data structure.
MongoDB는 기본적으로 B-tree 구조로 인덱스를 구성한다. 또한 자동으로 컬렉션은 _id (ObjectId) 필드를 활용하여 indexing을 한다.
이 때 RB-Tree는 하나의 노드에 최대 2개의 자식 노드만 가질 수 있어 많은 데이터를 저장해야되는 경우엔 적합하지 않다.
Hash Table도 인덱스를 구성하는 자료구조로 적합하지 않다. Hash Table은 많은 공간이 필요하기도 하고 정렬되어 있지 않기 때문에 부등호 연산이 자주 사용되는 데이터베이스 검색에는 적합하지 않다.
Reference
: )