ブラウザよりも高速アクセス！
19 関係: 基数木、奥村晴彦、二分探索、ハードディスクドライブ、ヌルポインタ、データベース管理システム、データ構造、ドナルド・クヌース、スプレー木、B*木、B+木、補助記憶装置、計算機科学、Kd木、R木、The Art of Computer Programming、木構造 (データ構造)、2-3-4木、2-3木。
基数木
right 基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。.
奥村晴彦
奥村 晴彦（おくむら はるひこ、1951年8月 - ）は、日本の工学者（計算機科学）。学位は博士（学術）（総合研究大学院大学・1999年）。三重大学教育学部教授・高等教育創造開発センター教授・総合情報処理センター教授。 松阪大学政治経済学部教授、松阪大学政策学部教授、核融合科学研究所客員教授、三重大学学長補佐（情報担当）などを歴任した。.
二分探索
二分探索（にぶんたんさく、binary search、BS）や二分検索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。.
ハードディスクドライブ
AT互換機用内蔵3.5インチHDD（シーゲイト・テクノロジー製） ハードディスクドライブ（hard disk drive, HDD）とは、磁性体を塗布した円盤を高速回転し、磁気ヘッドを移動することで、情報を記録し読み出す補助記憶装置の一種である。.
新しい！!: B木とハードディスクドライブ · 続きを見る »
ヌルポインタ
ヌルポインタ（null pointer）とは、何のオブジェクトも指していないことを表す特別なポインタである。 プログラムではヌルポインタを、不定長のリストの終端を表したり、何らかの動作の結果が失敗であることを表したりするのに使用する。後者の用法は、やのNothing値を使用することもできる。 ヌルポインタの値や型がいかなるものかという詳細は言語によって異なる。実際的にはいかなるオブジェクトも参照しないという言語もあり、参照先を求めようとするとJava（NullPointerException）のように例外が発生するものもある。 ヌルポインタはほとんどの処理系（この場合、言語処理系プログラムだけではなく、ハードウェアまでを含めて）で、内部的に0で表現されるが、ごく希に、0でない処理系もある。言語仕様上の意味としては普通「アドレス0（あるいは他のアドレス）を指し示すポインタ」ではなく、どこも指し示さないものとされる。 ヌルポインタを未初期化のポインタと混同してはならない。ヌルポインタは、あらゆる有効なオブジェクトとも異なることが保証されている。それに対し、言語や実装によっては、未初期化のポインタはそのような保証はなく、他のオブジェクトやヌルポインタと同じになる可能性がある。 ヌルポインタはヌル値とは意味が違う。ヌルポインタは多くのプログラミング言語において「値がない(no value)」ことを意味し、ヌル値はリレーショナルデータベースにおいて「未詳値(unknown value)」であることを意味する。ほとんどのプログラミング言語では2つのヌルポインタは等しいが、リレーショナルデータベースエンジンは2つのヌル値を等しいとはみなさない（それらは未詳値を表しているので、それらが等しいかどうかはわからない）。.
データベース管理システム
right データベース管理システム（データベースかんりシステム、DBMS; ）とは、コンピュータのデータベースを構築するために必要なデータベース運用、管理のためのシステム、およびそのソフトウェアのことである。データベースマネジメントシステムとも呼ばれる。.
新しい！!: B木とデータベース管理システム · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
ドナルド・クヌース
ドナルド・エルビン・クヌース（Donald Ervin Knuth, 1938年1月10日 -）は数学者、計算機科学者。スタンフォード大学名誉教授。 クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。 理論計算機科学への貢献とは別に、コンピュータによる組版システム TeX とフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。 作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。.
新しい！!: B木とドナルド・クヌース · 続きを見る »
スプレー木
プレー木（スプレーき、Splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。.
B*木
B*木（B*-tree）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。 B*木とB+木は異なる。後者は、葉ノードが連結されて連結リストを構成するようになっているものである。B+木は、挿入のコストを増大させて、検索を効率化したものである。 IEEEカンファレンスICCI '93 においては B**木の定義も見られた。.
B+木
簡単なB+木の例。1から7のキーとデータ値 d1-d7 がリンクされている。赤で示された連結リストによって順序通りの素早い走査が可能 B+木（B+ tree）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。 B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ b の記憶装置があるとき、b の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。 ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。.
補助記憶装置
パーソナルコンピュータのハードディスク 補助記憶装置（ほじょきおくそうち）は記憶装置の分類で、「主記憶装置」がコンピュータのメインのバスに直接接続され、CPUが即座にアクセスでき、演算の対象にもできる場合もあるのに対し、外部バスに接続され、CPUからは直接アクセスできないものを指す。レイテンシやスループットは遅いが比較すると大容量である。二次記憶装置などとも。.
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
Kd木
3次元の''k''d木。根セル（白）をまず2つの部分セルに分割（赤）し、それぞれをさらに2つに分割（緑）している。最後に4つのセルそれぞれを2つに分割（青）している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木（kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を''k''dトライと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。.
R木
2次元矩形のR木の例 R木（R-tree）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。.
The Art of Computer Programming
『』は、コンピュータプログラミングに関する書籍である。様々なアルゴリズムについて、その背景や歴史まで踏み込んだ徹底的な解説を行っている。著者のドナルド・クヌース は、自身のライフワークと位置づけている。 その全体構想から見れば現在も未完であるが、十分な業績としてみなされていることは、3巻初版までが刊行されていた1974年に受賞したチューリング賞の受賞理由に功績として本シリーズが含まれていることからも分かる。また、1976年に2巻の第2版の準備をしていた際に、初版のような鉛版による組版 (en:Hot metal typesetting) が行われなくなっていたために仕上がりに納得せず、組版システムの TeX を（当初は1978年のサバティカルが終わるまでには完全に仕上げるつもりで）作り始めてしまったことなど、逸話も多い。 現在3巻までと4巻の分冊が刊行されている。今後の計画についてはwebページで確認できるが、おおむね執筆開始当初の構想と変わっておらず、5巻は構文的 (syntactic) アルゴリズムについてで、9章が字句スキャナ、10章が（文字列）解析の技術、6巻は文脈自由文法の理論、7巻がコンパイラ技術となっている。ただし位置付けとして、5巻までの内容は central core of computer programming for sequential machines であるのに対し、6・7巻の内容は important but more specialized である、としている（またドラゴンブック等、この40年の間に書籍が充実した分野でもある）。 近年では、アスキーから日本語訳が出版されていた。2007年9月現在で3巻までと改訂版分冊1巻、4巻の分冊2,3が刊行されていた。その後、KADOKAWAドワンゴに在籍する元アスキーの編集者が担当する「アスキードワンゴ」レーベルにより、2015年6月の1巻再刊から再開され、2017年3月に4巻の最初のまとまった分冊である4A巻が刊行されている。 サイエンス社から出版されていた旧日本語訳版は、原著2巻相当分の4巻までしか出ていない。また、出版時期が古いためもあるが、専門用語について可能な限りカタカナ語を使わず訳すという少々冒険的な方針のために独特の用語が多用されており、和訳における専門用語の扱いにおける歴史的な一例にもなっている。.
新しい！!: B木とThe Art of Computer Programming · 続きを見る »
木構造 (データ構造)
親子構造 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。.
新しい！!: B木と木構造 (データ構造) · 続きを見る »
2-3-4木
2-3-4木（2-3-4き、2-3-4 tree）または2-4木は計算機科学の用語であり、4次のB木（B-tree）と同じである。 一般に2-3-4木はB木のように辞書として使うことができる平衡木の一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。 2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。 center.
2-3木
2-3木（-き）とは計算機科学におけるデータ構造で特に平衡木（balanced tree）に属する木構造の一種である。 2-3木（全ての要素を葉に持つパターン）.
