skillup

技術ブログ

Database

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

投稿日:2016年7月27日 更新日:

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

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

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

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

木構造とは?

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

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

2分木構造

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

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

メリット

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

デメリット

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

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

B木

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

 

-Database
-

執筆者:


comment

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

関連記事

no image

transactionが切れた場合のロックの復旧方法

transactionをスタートしたまま、commitせずにプログラムを途中で止めた場合の処理について。 不用意にプログラムを止めないようにしましょう。 Contents1 ロックのメカニズム1.1 …

no image

SQL基礎 条件式はunionよりもcaseで

複雑な条件式があったときにcase式を使うことでパフォーマンスを向上させることができます。 ※一般にunionを使うよりも高速なことが多い。 例1 ある条件により別の列を使いたいとき、 [crayon …

no image

MYSQL group_concat,cast等

実務でいろいろとトラブルがあり、データベースから在庫データを見てくれ~なんて依頼がありましたんでSQLをごりごり書いていたんですが、普段使わないようなSQLの構文を使ったのでここでちょっと紹介します。 …

no image

データベースアンチパターン・グレーパターンまとめ

本で勉強したものと自分で個人的に経験したことのまとめ Contents1 値渡しと参照渡しの混同2 型の制約が弱い3 変更していいデータ、していけないデータ4 参照系と履歴系のデータを区別する5 リレ …

no image

DBの基礎 テーブルとは

CSSを学習したあとはデータベースの学習などを。 参考図書:「達人に学ぶDB設計指南書」基本的にはこれを読んでいきます。が、現状よくわからないところは飛ばしていきます・・・ Contents1 テーブ …