Rustにおけるデータ構造の選択は、アプリケーションのパフォーマンスと保守性に直結する重要な要素です。

標準ライブラリで提供されているstd::collections::BTreeMapは、順序付けられたマップが必要な場面で非常に強力な武器となります。

多くの開発者は、高速な検索性能を求めてHashMapを第一の選択肢としがちですが、BTreeMapにはそれとは異なる独自の利点が存在します。

本記事では、BTreeMapの内部構造や、HashMapとの具体的な違い、そしてどのような場面で活用すべきかを詳しく解説します。

2026年現在のRust開発においても、これらのコレクションの使い分けはエンジニアの腕の見せ所と言えるでしょう。

目次 [ close ]
  1. BTreeMapの基本概念と内部構造
  2. HashMapとの決定的な違い
    1. 計算量とパフォーマンスの比較
    2. 順序の保持
    3. 比較表：BTreeMap vs HashMap
  3. BTreeMapの具体的な使い方
    1. 要素の挿入と取得
    2. 範囲検索（Range Queries）の活用
    3. Entry APIによる効率的な更新
  4. BTreeMapを選択すべきケース
    1. 1. ソートされたデータが必要な場合
    2. 2. 範囲スキャンを頻繁に行う場合
    3. 3. キーの順序で最小・最大値を求める場合
    4. 4. ハッシュ関数のコストを避けたい場合
  5. パフォーマンスに関する注意点
  6. まとめ

BTreeMapの基本概念と内部構造

BTreeMapは、その名の通り「B木（B-Tree）」というデータ構造をベースにしたマップ型コレクションです。

B木は、各ノードに複数の要素を格納し、ツリーの高さを低く抑えることでディスクI/Oやキャッシュ効率を最適化する性質を持っています。

Rustの標準ライブラリにおけるBTreeMapの実装は、メモリ上での動作を想定して高度に最適化されています。

B木の最大の特徴は、格納されたキーが常にソートされた状態に保たれることです。

これにより、最小値や最大値の取得、特定の範囲を指定したスキャンなどの操作を効率的に行うことが可能になります。

また、BTreeMapを使用するためには、キーとなる型がOrdトレイトを実装している必要があります。

これは、要素同士の大小比較が可能であることを保証するためであり、ハッシュ値を計算するHashMapの要件とは対照的です。

内部的なメモリ配置についても、BTreeMapは連結リストのような個別のノード割当を減らし、連続したメモリ領域を活用するように設計されています。

この設計により、モダンなCPUのL1/L2キャッシュを効率良く利用でき、ポインタを頻繁に追いかけることによるオーバーヘッドを最小限に抑えています。

HashMapとの決定的な違い

Rustでマップ構造を選択する際、最も比較対象となるのがHashMapです。

両者の違いを理解することは、適切なデータ構造を選択するための第一歩となります。

計算量とパフォーマンスの比較

HashMapは平均してO(1)の時間計算量で要素の挿入、検索、削除を実行します。

一方で、BTreeMapの計算量はO(log n)となります。

数値だけを見るとHashMapの方が有利に見えますが、ハッシュ関数の計算コストや衝突の影響を考慮する必要があります。

特に要素数が少ない場合や、ハッシュ計算が重い型をキーにする場合は、BTreeMapの方が高速に動作することもあります。

順序の保持

HashMapは要素をハッシュテーブルに格納するため、反復処理（イテレーション）を行った際の順序は不定です。

これに対し、BTreeMapは常にキーの順序に従って反復処理が行われます。

「キーの順番でデータを処理したい」という要件がある場合は、迷わずBTreeMapを選択すべきです。

比較表：BTreeMap vs HashMap

それぞれの特性を以下の表にまとめました。

特徴HashMapBTreeMap
平均時間計算量O(1)O(log n)
キーの要件Eq + HashOrd
順序性なし（不定）あり（ソート済み）
範囲検索不可能可能（高速）
メモリ使用効率バケットの空きが必要比較的コンパクト

BTreeMapの具体的な使い方

ここでは、RustでのBTreeMapの基本的な操作方法をプログラム例とともに紹介します。

要素の挿入と取得

まずは、最も基本的な値の追加と取得の方法を見ていきましょう。

Rust
use std::collections::BTreeMap;

fn main() {
    // BTreeMapのインスタンス化
    let mut scores = BTreeMap::new();

    // 要素の挿入
    scores.insert("Blue", 10);
    scores.insert("Red", 50);
    scores.insert("Green", 25);

    // キーがソートされているため、反復処理はアルファベット順になる
    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }

    // 値の取得
    if let Some(score) = scores.get("Red") {
        println!("Redのスコアは {} です", score);
    }
}
実行結果
Blue: 10
Green: 25
Red: 50
Redのスコアは 50 です

実行結果から分かる通り、挿入した順番に関わらず、キー（文字列）の辞書順で出力されています。

範囲検索（Range Queries）の活用

BTreeMapの真価を発揮するのが、特定の範囲のキーを持つ要素だけを抽出する範囲検索です。

rangeメソッドを使用することで、柔軟なフィルタリングが可能です。

Rust
use std::collections::BTreeMap;

fn main() {
    let mut store = BTreeMap::new();
    store.insert(100, "Item A");
    store.insert(200, "Item B");
    store.insert(300, "Item C");
    store.insert(400, "Item D");
    store.insert(500, "Item E");

    // 200以上、400未満の要素を取得
    println!("Range 200..400:");
    for (id, name) in store.range(200..400) {
        println!("{}: {}", id, name);
    }

    // 300以上のすべての要素を取得
    println!("Range 300..:");
    for (id, name) in store.range(300..) {
        println!("{}: {}", id, name);
    }
}
実行結果
Range 200..400:
200: Item B
300: Item C
Range 300..:
300: Item C
400: Item D
500: Item E

このように、数値範囲や時間、アルファベット範囲などでデータを効率的にスキャンしたい場合に非常に便利です。

Entry APIによる効率的な更新

値が存在しない場合のみデフォルト値を挿入したり、既存の値を更新したりする場合、entry APIを使用するのがRustの流儀です。

Rust
use std::collections::BTreeMap;

fn main() {
    let mut word_counts = BTreeMap::new();
    let text = "apple banana apple cherry banana apple";

    for word in text.split_whitespace() {
        // キーが存在すればカウントアップ、なければ0を挿入してからカウントアップ
        word_counts.entry(word).and_modify(|count| *count += 1).or_insert(1);
    }

    println!("{:?}", word_counts);
}
実行結果
{"apple": 3, "banana": 2, "cherry": 1}

BTreeMapを選択すべきケース

開発においてBTreeMapを優先的に選ぶべき具体的なシチュエーションを整理します。

1. ソートされたデータが必要な場合

表示画面で常にリストがソートされている必要がある、あるいは順序に依存したアルゴリズムを実装している場合は、BTreeMapが最適です。

HashMapからデータを取得した後に別途ソートを行うよりも、挿入時にソート状態を維持する方が効率的なケースが多いです。

2. 範囲スキャンを頻繁に行う場合

「直近1時間のログを取得する」「ID 1000番から2000番までのユーザーをリストアップする」といったクエリが必要なシステムでは、B木構造が威力を発揮します。

データベースのインデックスのような役割をアプリケーション内で持たせたい場合に適しています。

3. キーの順序で最小・最大値を求める場合

BTreeMapは最小値や最大値へのアクセスが容易です。

first_key_valueやlast_key_valueといったメソッド（Nightlyや近年の安定版で利用可能）を使用すれば、効率的に端点データを取得できます。

4. ハッシュ関数のコストを避けたい場合

非常に長い文字列や、複雑な構造体をキーにする場合、ハッシュ値の計算自体がボトルネックになることがあります。

一方で比較処理（Ord）がシンプルであれば、BTreeMapの方がスループットが向上する可能性があります。

パフォーマンスに関する注意点

強力なBTreeMapですが、あらゆる場面で万能というわけではありません。

計算量が対数時間（log n）であるため、数百万、数千万といった巨大なデータセットでは、定数時間（O(1)）のHashMapに速度で劣る場面が増えます。

また、B木はノードの分割や結合が発生するため、書き込み（挿入・削除）のワークロードが極めて高い場合、ハッシュテーブルよりも再平衡化のコストが目立つことがあります。

メモリアロケーションについても、BTreeMapはノード単位での管理となるため、データの密度によってはHashMapよりもオーバーヘッドが大きくなる場合があります。

ただし、RustのBTreeMapは各ノードに多くの要素を詰め込むことで、このデメリットを最小限に抑えています。

まとめ

RustのBTreeMapは、単なる「遅いマップ」ではなく、「順序」と「範囲」を管理するための高度なデータ構造です。

HashMapがランダムアクセスに特化しているのに対し、BTreeMapはデータの流れや連続性を重視するシーンで真価を発揮します。

順序付きイテレーション、範囲検索、そしてキャッシュ効率を意識した設計は、Rustが掲げる「ゼロコスト抽象化」を体現していると言えるでしょう。

どちらのマップを使うべきか迷った際は、まずはデータのアクセスパターンを分析してみてください。

単一のキー検索が中心ならHashMapを、データの順序や範囲が重要ならBTreeMapを選択するのがベストプラクティスです。

2026年のRustエコシステムにおいても、これらの特性を正しく理解し使い分けるスキルは、高品質なソフトウェア開発に欠かせません。

適切なデータ構造を選ぶことで、Rustの持つポテンシャルを最大限に引き出していきましょう。