skillup

技術ブログ

Database

データ構造の基礎知識 後編 木構造

投稿日:

データベースの学習をしていたときの復習です。

データ構造の基礎知識 前編 メモリとポインタ、配列と連結リスト

データ構造の基礎知識 中編 ハッシュ

今回はもう少し複雑な「木構造」について考えてみます。

木構造とは?

下記のような特徴があります。

  • 要素同士に親子関係がある
  • 親は複数の子を持てる
  • 子から親へ循環して親子関係になることはない

2分木構造

  • 親は0~2個の子供を持つ
  • 大小関係は左の数<親<右の数となる

下記リンクが一番イメージしやすい。

http://tokyo-ct.net/usr/kosaka/for_students/jissen1/akiyojissen1/kougi13.html

メリット

  • キーが常にソート済み
  • 各要素へのアクセスがO(logn)
  • 要素を追加してもハッシュのようなrehashは不要
  • ハッシュと違い、無駄になるメモリがないためメモリ効率が良い

デメリット

  • 偏った木構造(枝が一本のみ)の場合,O(n)になる

そこでこのデメリットを補うために、B木という構造が使われます。

B木

  • 各ノード内では値はソート済みの状態で保存されている
  • 各値の左側から生えている枝からたどれる値はその値よりも小さい値
  • 各値の右側から生えている枝からたどれる値はその値よりも大きい値

参照リンク

http://www.moon.sannet.ne.jp/okahisa/b-tree/

-Database
-

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

正規化のデメリット

Contents1 正規化のデメリット2 本日のSQL 正規化のデメリット 正規化についていろいろ書いてきましたが、メリットもあればデメリットもあります。 メリットとしては データの不整合が起きにくい …

no image

リレーションを含んだテーブルでの副問い合わせ

本日はSQLネタです。 下記のようなテーブル構成があったときとします。 注文ヘッダと注文詳細は(1:N)とします。 ここで、product_id=5を含んだ注文ヘッダーレコードを取り出したいとします。 …

no image

JPAでの多対多のリレーション

以前、このエントリーでJPAのリレーションについて説明しました。 今回は多対多について説明します。 Contents1 テーブル構成2 ソース2.1 CDのエンティティ2.2 Artistのエンティテ …

no image

アンチパターン バインド変数の未使用+直積組み合わせ+データ量爆発+インデックス関連

本日はSQLコーディングに関して。 ここら辺は実際にプログラムを書く際に重要になってくるネタ。 Contents1 バインド変数1.1 デメリット1.2 対策2 直積により組み合わせが爆発する2.1 …

no image

データベースの権限設定

データベースを作成するときに

と入力していますが、ほぼ機械的にこれを売っているのでこれを機にどんな使い方があるのかを調べてみました。 …