データ構造のおさらい(コレクション、2分探索木、B木、B+木)
データ構造
-雑誌で読んだことをまとめておく、その一環
配列とコレクション
配列
- 複数データを連続して格納
連結リスト
- 各要素が自分自身の値と 次の要素への参照を持っ ているのが連結リスト
ハッシュテーブル
- ハッシュテーブルという名のとおり、「ハッシュ関 数」と呼ばれる種類の関数が利用されているのが特徴
ハッシュテーブルという名のとおり、「ハッシュ関 数」と呼ばれる種類の関数が利用されているのが特徴
インデックス
2分探索木
- 右が大きい、左が小さいの約束でそーと
B木
- 工夫しない単なる2分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れる
- ルートノードと子ノードの各ページは、キー値と子ノードへのポインタを持つ
- リーフノードの各ページは、キー値とデータへのポインタを持つ (B+ treeの場合、データを持つのはリーフノードだけ)
B+木
- リーフノードとリーフノードを結ぶポインタがある
- データはリーフノードのみに保持する