Index 트레이트는 Rust에서 컬렉션을 인덱싱하여 값을 접근할 수 있게 해주는 표준 트레이트입니다. 이 트레이트는 대괄호([])를 사용해 컬렉션의 요소를 조회하는 기능을 제공합니다. 벡터, 슬라이스, 해시맵 등 다양한 자료구조가 이 Index 트레이트를 구현하고 있으며, 인덱스를 사용해 값에 접근할 수 있습니다.

Index 트레이트의 정의

Index 트레이트는 다음과 같이 정의되어 있습니다:

pub trait Index<Idx> {
    type Output;

    fn index(&self, index: Idx) -> &Self::Output;
}

구성 요소

1. Idx:
   • Index 트레이트는 제네릭 인덱스 타입 Idx를 사용합니다. 이는 컬렉션에 따라 달라질 수 있는 인덱스 타입을 나타냅니다.
   • 예를 들어, 벡터는 usize를 인덱스로 사용하지만, 해시맵은 키(K)를 인덱스로 사용합니다.
2. Output:
   • Output은 해당 인덱스 타입으로 조회한 결과 값의 타입을 나타냅니다.
   • 예를 들어, 벡터에서는 인덱스로 접근한 요소의 타입이 Output이 됩니다.
3. index(&self, index: Idx) -> &Self::Output:
   • 이 메서드는 주어진 인덱스(Idx)에 대한 값을 참조로 반환합니다.
   • self는 불변 참조로 전달되므로, 이 메서드는 값을 변경하지 않고 조회만 합니다.

B-트리의 원리

• *B-트리(B-tree)**는 균형 잡힌 트리 구조로, 노드 안에 여러 개의 키와 자식 포인터를 포함하는 다진 트리입니다. 데이터베이스나 파일 시스템과 같은 대용량 데이터 구조에서 주로 사용됩니다. B-트리는 검색, 삽입, 삭제 등의 연산에서 효율적이며, 특히 디스크나 메모리 계층에서 입출력 효율을 극대화할 수 있습니다.

B-트리의 주요 특징

1. 균형 유지:
   • B-트리는 항상 균형을 유지합니다. 이는 트리의 모든 리프 노드가 동일한 깊이에 위치한다는 뜻입니다. 이 때문에 트리의 높이는 매우 낮아지며, 삽입이나 삭제 시 재정렬 작업이 발생하더라도 성능이 안정적입니다.
2. 다수의 자식 노드:
   • 각 노드는 여러 개의 키와 **포인터(자식 노드에 대한 링크)**를 가집니다. 일반적인 이진 트리와 달리, B-트리에서는 하나의 노드가 여러 개의 자식 노드를 가질 수 있습니다.
   • 트리의 **차수(order)**는 각 노드가 가질 수 있는 최대 자식 노드의 수를 의미합니다. 예를 들어, 차수가 M인 B-트리에서는 각 노드가 최대 M-1개의 키를 가지고, 최대 M개의 자식 노드를 가집니다.
3. 노드 내 정렬:
   • 각 노드 내에서 키들은 항상 오름차순으로 정렬되어 있습니다. 이렇게 정렬되어 있기 때문에 이진 탐색을 통해 빠르게 원하는 키를 찾을 수 있습니다.
4. 효율적인 탐색:
   • B-트리는 노드 내에서 이진 탐색을 사용하여 키를 검색합니다. 트리의 높이가 낮기 때문에, 최악의 경우에도 O(log N) 시간 복잡도로 탐색이 가능합니다.

B-트리의 동작 원리

1. 삽입:

• 새 키를 삽입할 때, 해당 키가 들어갈 리프 노드를 찾아 삽입합니다.
• 만약 리프 노드가 가득 찼다면, 노드를 분할하고, 가운데 값을 부모 노드로 올립니다.