MongoDB에서 Index (B-tree)

업무에서 발생한 일을 바탕으로 프롬프트를 작성하고 정리한 내용.

cs수업때 b+tree 배운 이후에 까먹고 있었는데, 리마인드 할 겸 기록해둔다.

직접 작성하는 것보다 더 나은 것 같다.

 

---

MongoDB 인덱스와 B-Tree: OOM 에러로부터 배운 교훈

얼마 전 MongoDB를 사용하면서 예상치 못한 Out of Memory(OOM) 에러를 경험했습니다. 이 문제는 단순히 History 데이터를 정렬(sort)하려는 작업에서 발생했으며, 원인은 특정 필드에 대해 인덱스가 없었기 때문입니다. 이 사건을 계기로 MongoDB에서 사용하는 인덱스의 구조를 자세히 알아보게 되었고, 그 핵심에 B-Tree라는 자료 구조가 있음을 알게 되었습니다. 이번 글에서는 MongoDB 인덱스에서 사용되는 B-Tree와 관련 개념을 소개하고, B+Tree와의 차이점까지 자세히 다뤄보겠습니다.

---

OOM 에러 발생: 왜 인덱스가 중요할까?

MongoDB에서 데이터 정렬은 매우 자주 수행되는 작업입니다.

하지만 정렬할 필드에 적절한 인덱스가 없을 경우, MongoDB는 정렬을 메모리에서 처리합니다.

이 과정에서 데이터가 많으면 메모리 사용량이 급증해 OOM 에러가 발생할 수 있습니다.

제 경우에는 History 데이터를 createdAt 필드로 정렬하다가 문제가 발생했는데, 인덱스가 없었기 때문에 32MB 메모리 제한을 초과해 오류가 발생했습니다.

 

해결 방법은 간단했습니다: createdAt 필드에 인덱스를 추가했습니다.

// createdAt 필드에 인덱스 추가
model.History.createIndex({ createdAt: 1 });

이렇게 간단히 문제를 해결한 후, MongoDB 인덱스가 어떻게 동작하는지 궁금해졌습니다.

이를 조사하면서 MongoDB가 인덱스를 구현하는 데 B-Tree를 사용한다는 사실을 알게 되었습니다.

---

B-Tree란 무엇인가?

**B-Tree(Balanced Tree)**는 데이터베이스와 파일 시스템에서 널리 사용되는 자료 구조입니다. 이진 트리(Binary Tree)의 일반화된 형태로, 효율적인 검색, 삽입, 삭제를 보장합니다.

B-Tree의 주요 특징

1. 균형 유지: 모든 리프 노드가 동일한 깊이에 위치하여 항상 균형을 유지합니다.
2. 다중 자식 노드: 한 노드가 여러 자식을 가질 수 있습니다(차수 m).
3. 범위 검색 지원: 노드 내 키가 정렬되어 있어 범위 쿼리에 적합합니다.
4. 낮은 트리 높이: 트리의 높이가 낮아 디스크 I/O를 최소화하고 검색 속도를 높입니다.

B-Tree의 구조

• 각 노드는 키와 포인터로 구성됩니다.
• 노드는 최소 ⌈m/2⌉개의 키와 최대 m-1개의 키를 가질 수 있습니다.
• 루트 노드는 최소 1개의 키를 가집니다.

B-Tree 동작 예제

삽입 예제:

1. 아래와 같은 B-Tree를 생각해봅시다 (차수 3):

     [10]
   /    \
 [5]    [15, 20]

1. 25를 삽입하려면 [15, 20] 노드에 추가됩니다:

     [10]
   /    \
 [5]    [15, 20, 25]

1. 노드가 초과되면(키 개수 > 2), 중간 값(20)을 부모로 올립니다:

       [10, 20]
      /    |    \
   [5]   [15]   [25]

---

B-Tree vs B+Tree: 무엇이 다를까?

B+Tree는 B-Tree의 변형으로, 데이터베이스와 파일 시스템에서 더 자주 사용됩니다. 두 자료 구조는 비슷하지만, 데이터 저장 방식과 범위 검색 성능에서 차이가 있습니다.

 

B-Tree와 B+Tree의 차이점

특징	B-Tree	B+Tree
데이터 저장 위치	모든 노드	리프 노드에만 저장
리프 노드 연결	연결되지 않음	연결 리스트로 연결
범위 검색 성능	중간 노드도 탐색해야 함	리프 노드 연결로 빠른 탐색 가능
노드 크기	키와 데이터 모두 저장	키만 저장 (비교적 작음)
구조 단순성	구조가 단순	추가적인 연결 리스트로 구조가 더 복잡

 

B+Tree의 범위 검색 예제

B+Tree는 모든 데이터가 리프 노드에 저장되고, 리프 노드가 연결 리스트로 연결되어 있기 때문에 범위 검색이 효율적입니다.

 

B+Tree 예제:

1. 아래와 같은 B+Tree가 있다고 가정합니다 (차수 3):

      [20]
     /    \
[10]        [30, 40]
 |            |    |
[5, 10, 15]  [25] [35, 40, 45]

1. 데이터가 리프 노드에만 저장되며, 리프 노드는 연결 리스트로 연결되어 있습니다:

[5, 10, 15] <-> [25] <-> [35, 40, 45]

1. 10 <= x <= 35 범위를 검색하려면:
   • 10이 포함된 리프 노드부터 시작합니다.
   • 연결 리스트를 따라가며 데이터를 수집합니다.
   • 결과: [10, 15, 25, 35]

이 방식은 중간 노드를 탐색하지 않기 때문에 B-Tree보다 빠릅니다.

---

MongoDB와 B-Tree: 우리가 얻은 것

MongoDB는 기본적으로 B-Tree를 기반으로 인덱스를 구현합니다. B-Tree의 장점 덕분에:

1. 정렬과 검색 성능이 향상됩니다.
2. 범위 쿼리가 효율적입니다.
3. 데이터가 증가해도 트리 높이가 낮아 성능이 일정하게 유지됩니다.

하지만, 잘못된 인덱스 설계는 문제가 될 수 있습니다. 이번 경험을 통해 배운 가장 중요한 교훈은, 쿼리 패턴에 맞는 적절한 인덱스를 설계하는 것의 중요성입니다.

---

마무리

OOM 에러는 성가신 문제였지만, 이를 통해 MongoDB의 내부 작동 원리와 B-Tree의 중요성을 깊이 이해할 수 있는 계기가 되었습니다. 더 나아가 B-Tree와 B+Tree의 차이점까지 알게 되었으니, 앞으로 인덱스를 설계할 때 더 나은 선택을 할 수 있을 것입니다.

여러분도 데이터베이스 성능 문제를 겪고 있다면, 인덱스를 점검하고 B-Tree 구조를 한 번 살펴보세요. 큰 도움이 될 것입니다!

 

 

 

 

+) B+tree가 더 좋아보이는데 왜 MongoDB는 B-tree를 사용했는가?

 

MongoDB가 B-Tree를 사용하는 이유는 설계 시점의 기술적 맥락과 사용 사례에 따른 선택에서 기인합니다.

1. B-Tree의 성숙도와 단순성
   MongoDB는 초기 설계 당시(2009년) 안정성과 효율성이 검증된 B-Tree를 채택했습니다.
   • B-Tree는 범용적인 데이터베이스에서 폭넓게 사용되며, 구현이 비교적 간단하고 검증된 자료 구조입니다.
   • 많은 시스템이 B-Tree 기반이라, 이미 성숙한 알고리즘과 최적화된 디스크 접근 방식이 존재했습니다.
2. B+Tree와 비교한 장단점
   • 데이터 저장: B+Tree는 데이터를 리프 노드에만 저장해 범위 쿼리에 유리하지만, 이로 인해 디스크 I/O가 약간 더 늘어날 수 있습니다. 반면 B-Tree는 모든 노드에 데이터를 저장하기 때문에 검색 시 중간 노드에서 필요한 데이터를 더 빨리 찾을 가능성이 있습니다.
   • 범위 쿼리 중요성: B+Tree는 범위 검색에 최적화되어 있지만, MongoDB는 단일 검색 및 랜덤 액세스에 더 중점을 둔 설계를 했습니다.
   • 복잡성: B+Tree는 리프 노드 간 연결 리스트가 필요하여 구조가 더 복잡합니다. MongoDB는 초기에는 단순성과 구현 속도를 우선시했을 가능성이 큽니다.
3. MongoDB의 사용 패턴
   MongoDB는 문서 기반 데이터베이스로, 대량의 쓰기 작업과 비정형 데이터를 처리하는 데 최적화되어 있습니다.
   • 초기 설계에서 범위 검색보다는 단일 값 검색과 효율적인 쓰기 성능에 집중했을 가능성이 있습니다.
   • 또한, B-Tree도 범위 검색에 충분히 효과적이기 때문에, 반드시 B+Tree를 선택해야 할 필요가 없었습니다.
4. 현대의 MongoDB
5. MongoDB는 이후에도 B-Tree를 유지하면서 추가 최적화를 통해 높은 성능을 제공하고 있습니다.
   B+Tree의 이점은 일부 시스템에서는 더 유용할 수 있지만, MongoDB의 데이터 모델과 쿼리 패턴에서 B-Tree는 여전히 효율적인 선택입니다.

https://www.mongodb.com/ko-kr/docs/manual/indexes/