JP2596397B2 - 木構造データ格納方式 - Google Patents
木構造データ格納方式Info
- Publication number
- JP2596397B2 JP2596397B2 JP6339243A JP33924394A JP2596397B2 JP 2596397 B2 JP2596397 B2 JP 2596397B2 JP 6339243 A JP6339243 A JP 6339243A JP 33924394 A JP33924394 A JP 33924394A JP 2596397 B2 JP2596397 B2 JP 2596397B2
- Authority
- JP
- Japan
- Prior art keywords
- node
- tree structure
- data
- nodes
- structure data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【０００１】
【産業上の利用分野】本発明はアクセス速度の高速化を
図るために外部記憶装置上のデータの一部を主記憶上に
配置するようにした情報処理装置に関し、特に木構造デ
ータを対象としてその一部を主記憶上に配置する木構造
データ格納方式に関する。
図るために外部記憶装置上のデータの一部を主記憶上に
配置するようにした情報処理装置に関し、特に木構造デ
ータを対象としてその一部を主記憶上に配置する木構造
データ格納方式に関する。
【０００２】
【従来の技術】情報処理装置で扱うデータ構造の一種
に、木構造データがある。木構造データは、ルートとな
るノードを出発点として、複数のノードをポインタで逆
木状に連結したものであり、親子関係，上下関係を有す
るデータを記述するのに適していることから各種の分野
で利用されている。
に、木構造データがある。木構造データは、ルートとな
るノードを出発点として、複数のノードをポインタで逆
木状に連結したものであり、親子関係，上下関係を有す
るデータを記述するのに適していることから各種の分野
で利用されている。
【０００３】ところで、木構造データに限らず、一般に
データをアクセスする場合、それが主記憶上にあった方
がディスク装置等の外部記憶装置上にある場合よりも高
速にアクセスできる。このため、外部記憶装置と主記憶
とを有する情報処理装置において、主記憶容量の制限か
ら外部記憶装置に格納された木構造データの全てを主記
憶上に置くことができない場合、外部記憶装置上に格納
された木構造データのうち頻繁にアクセスされるデータ
だけを主記憶上に置くことで、アクセス速度の高速化を
図っている。そして、主記憶上に配置するデータの従来
の決定方式としては、最近にアクセスされたデータほど
優先的に配置する方式や、今までアクセスされた回数が
多いデータほど優先的に配置する方式等が採用されてい
る。
データをアクセスする場合、それが主記憶上にあった方
がディスク装置等の外部記憶装置上にある場合よりも高
速にアクセスできる。このため、外部記憶装置と主記憶
とを有する情報処理装置において、主記憶容量の制限か
ら外部記憶装置に格納された木構造データの全てを主記
憶上に置くことができない場合、外部記憶装置上に格納
された木構造データのうち頻繁にアクセスされるデータ
だけを主記憶上に置くことで、アクセス速度の高速化を
図っている。そして、主記憶上に配置するデータの従来
の決定方式としては、最近にアクセスされたデータほど
優先的に配置する方式や、今までアクセスされた回数が
多いデータほど優先的に配置する方式等が採用されてい
る。
【０００４】
【発明が解決しようとする課題】これらの従来技術は、
何れも現在までのアクセス状況を基に将来のアクセス状
況を推測するものであるため、個々のデータがアクセス
される毎にそのアクセス状況の記録を取っておく必要が
あり、また主記憶データの入れ換え時には個々のデータ
のアクセス状況の記録を参照して主記憶から追い出すデ
ータを決定する処理が必要となり、データアクセス時の
オーバヘッドが大きくなるという問題点がるある。
何れも現在までのアクセス状況を基に将来のアクセス状
況を推測するものであるため、個々のデータがアクセス
される毎にそのアクセス状況の記録を取っておく必要が
あり、また主記憶データの入れ換え時には個々のデータ
のアクセス状況の記録を参照して主記憶から追い出すデ
ータを決定する処理が必要となり、データアクセス時の
オーバヘッドが大きくなるという問題点がるある。
【０００５】本発明は木構造データを扱う情報処理装置
におけるこのような問題点を改善したもので、その目的
は、主記憶上に配置すべき木構造データ部分をデータア
クセス時のオーバヘッド無しに決定することができるよ
うにした木構造データ格納方式を提供することにある。
におけるこのような問題点を改善したもので、その目的
は、主記憶上に配置すべき木構造データ部分をデータア
クセス時のオーバヘッド無しに決定することができるよ
うにした木構造データ格納方式を提供することにある。
【０００６】
【課題を解決するための手段】本発明はアクセス速度の
高速化を図るために外部記憶装置上のデータの一部を主
記憶上に配置するようにした情報処理装置において、前
記外部記憶装置に格納された木構造データを対象とし、
そのノードのうち子孫ノード数の多いものを優先的に前
記主記憶上に配置するノード配置部を備えるようにして
いる。
高速化を図るために外部記憶装置上のデータの一部を主
記憶上に配置するようにした情報処理装置において、前
記外部記憶装置に格納された木構造データを対象とし、
そのノードのうち子孫ノード数の多いものを優先的に前
記主記憶上に配置するノード配置部を備えるようにして
いる。
【０００７】
【作用】木構造データは、親子関係，上下関係を有する
データを記述するのに適したデータ構造であるため、そ
のアクセス時には一般にルートとなるノードに近いデー
タほど良くアクセスされる傾向を持つ。即ち、オブジェ
クト指向における継承では、親ノードの属性はその子ノ
ードに継承されるため、或るノードの属性を知るための
アクセスでは、その親ノードもルートまで辿ってアクセ
スしている。また、検索などではルートノードから検索
が開始されるためルートノードに近いデータほど頻繁に
アクセスされる傾向がある。本発明はこのような点に着
目したもので、ノード配置部が、外部記憶装置に格納さ
れた木構造データのノードのうち子孫ノード数が多いも
のを優先的に主記憶上に配置することにより、アクセス
先ノードが主記憶上に存在する確率を高め、アクセス速
度の向上を図っている。
データを記述するのに適したデータ構造であるため、そ
のアクセス時には一般にルートとなるノードに近いデー
タほど良くアクセスされる傾向を持つ。即ち、オブジェ
クト指向における継承では、親ノードの属性はその子ノ
ードに継承されるため、或るノードの属性を知るための
アクセスでは、その親ノードもルートまで辿ってアクセ
スしている。また、検索などではルートノードから検索
が開始されるためルートノードに近いデータほど頻繁に
アクセスされる傾向がある。本発明はこのような点に着
目したもので、ノード配置部が、外部記憶装置に格納さ
れた木構造データのノードのうち子孫ノード数が多いも
のを優先的に主記憶上に配置することにより、アクセス
先ノードが主記憶上に存在する確率を高め、アクセス速
度の向上を図っている。
【０００８】ここで、ルートノードに近いノードほど優
先的に主記憶上に配置するのではなく、子孫ノード数の
多いものほど優先的に配置するようにしたのは、例え
ば、ルートノードに２つのノードが接続されており、そ
の一方のノードにはその下に数多くの子孫ノードが接続
されているのに対し、他方のノードは子孫ノードを１つ
も持たない葉ノードであった場合、ルートノードに近い
ノードを優先すると、この葉のノードも主記憶上に格納
されてしまうことになるからである。
先的に主記憶上に配置するのではなく、子孫ノード数の
多いものほど優先的に配置するようにしたのは、例え
ば、ルートノードに２つのノードが接続されており、そ
の一方のノードにはその下に数多くの子孫ノードが接続
されているのに対し、他方のノードは子孫ノードを１つ
も持たない葉ノードであった場合、ルートノードに近い
ノードを優先すると、この葉のノードも主記憶上に格納
されてしまうことになるからである。
【０００９】
【実施例】次に本発明の実施例について図面を参照して
詳細に説明する。
詳細に説明する。
【００１０】図１を参照すると、本発明の一実施例の木
構造データ格納方式を適用した情報処理装置の一例は、
ＣＰＵ等を含む処理装置１と、これに接続されたディス
ク装置２および主記憶３と、ディスク装置２上の木構造
データの一部を主記憶３上に配置するノード配置部４と
から構成されている。また、ノード配置部４は、子孫ノ
ード数算出手段４１とノード選択手段４２とノード読み
出し手段４３とで構成されている。
構造データ格納方式を適用した情報処理装置の一例は、
ＣＰＵ等を含む処理装置１と、これに接続されたディス
ク装置２および主記憶３と、ディスク装置２上の木構造
データの一部を主記憶３上に配置するノード配置部４と
から構成されている。また、ノード配置部４は、子孫ノ
ード数算出手段４１とノード選択手段４２とノード読み
出し手段４３とで構成されている。
【００１１】図２にディスク装置２に格納されている木
構造データの一例を示す。同図において、左側に記載し
た部分が木構造データの木構造管理情報であり、この例
では１０個のノードＮ１〜Ｎ１０から構成されている。
また、右側に記載した部分が木構造データのデータ部分
であり、各ノードＮ１〜Ｎ１０と１対１に対応するエリ
アＤ１〜Ｄ１０から構成されている。木構造管理情報に
おけるノード間はその親子関係に従ってリンクされてお
り、個々のノードＮ１〜Ｎ１０に保持すべき実際のデー
タは図示の矢印で示すようにポインタが指し示すエリア
Ｄ１〜Ｄ１０に格納されている。
構造データの一例を示す。同図において、左側に記載し
た部分が木構造データの木構造管理情報であり、この例
では１０個のノードＮ１〜Ｎ１０から構成されている。
また、右側に記載した部分が木構造データのデータ部分
であり、各ノードＮ１〜Ｎ１０と１対１に対応するエリ
アＤ１〜Ｄ１０から構成されている。木構造管理情報に
おけるノード間はその親子関係に従ってリンクされてお
り、個々のノードＮ１〜Ｎ１０に保持すべき実際のデー
タは図示の矢印で示すようにポインタが指し示すエリア
Ｄ１〜Ｄ１０に格納されている。
【００１２】処理装置１がディスク装置２に格納された
木構造データに対する処理を開始するのに先立って、ノ
ード配置部４は、ディスク装置２上の木構造データの一
部を主記憶３上のデータ部３１に配置し、且つ、その配
置状況に合致した木構造管理情報を管理部３２に設定す
る。このような動作は以下のように行われる。
木構造データに対する処理を開始するのに先立って、ノ
ード配置部４は、ディスク装置２上の木構造データの一
部を主記憶３上のデータ部３１に配置し、且つ、その配
置状況に合致した木構造管理情報を管理部３２に設定す
る。このような動作は以下のように行われる。
【００１３】先ず、ノード配置部４の子孫ノード数算出
手段４１は、ディスク装置２に格納された木構造データ
の各ノードの子孫ノード数を算出する。次に、この算出
結果に基づき、ノード選択手段４２が、子孫ノード数の
多いものから順にＬ個のノードを選択する。ここで、Ｌ
個はデータ部３１のサイズによって決定され、データ部
３１に入り切る範囲内でできるだけ多くのノードが選択
される。そして、ノード読み出し手段４３が、ノード選
択手段４２で選択されたノードのデータをディスク装置
２から読み出して主記憶３のデータ部３１に格納し、そ
の格納先のデータを指し示すように木構造管理情報のポ
インタを変更した木構造管理情報を管理部３２に格納す
る。
手段４１は、ディスク装置２に格納された木構造データ
の各ノードの子孫ノード数を算出する。次に、この算出
結果に基づき、ノード選択手段４２が、子孫ノード数の
多いものから順にＬ個のノードを選択する。ここで、Ｌ
個はデータ部３１のサイズによって決定され、データ部
３１に入り切る範囲内でできるだけ多くのノードが選択
される。そして、ノード読み出し手段４３が、ノード選
択手段４２で選択されたノードのデータをディスク装置
２から読み出して主記憶３のデータ部３１に格納し、そ
の格納先のデータを指し示すように木構造管理情報のポ
インタを変更した木構造管理情報を管理部３２に格納す
る。
【００１４】以後、処理装置１は、主記憶３の管理部３
２に存在する木構造管理情報を参照しながら、木構造デ
ータをアクセスして処理を行う。
２に存在する木構造管理情報を参照しながら、木構造デ
ータをアクセスして処理を行う。
【００１５】図３はノード配置部４の子孫ノード数算出
手段４１の処理例を示すフローチャートである。同図に
おいて、ステップＳ１〜Ｓ４はルートのノードに近いノ
ードほど、より小さい番号の添字ｉを持つノード名ａi
を付ける処理であり、ステップＳ５〜Ｓ８は各ノードの
子孫ノード数を算出する処理である。以下、図２に示し
た木構造データを例にして、子孫ノード数算出手段４１
の動作を説明する。
手段４１の処理例を示すフローチャートである。同図に
おいて、ステップＳ１〜Ｓ４はルートのノードに近いノ
ードほど、より小さい番号の添字ｉを持つノード名ａi
を付ける処理であり、ステップＳ５〜Ｓ８は各ノードの
子孫ノード数を算出する処理である。以下、図２に示し
た木構造データを例にして、子孫ノード数算出手段４１
の動作を説明する。
【００１６】子孫ノード数算出手段４１は、先ず、ルー
トとなるノードＮ１に添字１を持つノード名ａ1 を付与
し、このノードを着目ノードａs とする（Ｓ１）。次
に、このノード名ａ1 を付与したノードＮ１に隣接する
ノードで未だ名前の付いていない全てのノードに名前ａ
k （ｋは直前に使用された番号の次の番号から順に振ら
れる番号である）を付与する（Ｓ２）。図２の場合、ノ
ードＮ１に隣接するノードで名前の無いノードはＮ２だ
けなので、ノードＮ２に名前ａ2 を付ける。次に、名前
の付いたノードで且つ隣接するノードに名前の付いてい
ないノードの１つを着目ノードａs とし（Ｓ４）、ステ
ップＳ２に戻る。図２の場合、名前の付いたノードで且
つ隣接するノードに名前の付いていないノードはＮ２な
ので、ノードＮ２を着目ノードａs としてステップＳ２
に戻る。
トとなるノードＮ１に添字１を持つノード名ａ1 を付与
し、このノードを着目ノードａs とする（Ｓ１）。次
に、このノード名ａ1 を付与したノードＮ１に隣接する
ノードで未だ名前の付いていない全てのノードに名前ａ
k （ｋは直前に使用された番号の次の番号から順に振ら
れる番号である）を付与する（Ｓ２）。図２の場合、ノ
ードＮ１に隣接するノードで名前の無いノードはＮ２だ
けなので、ノードＮ２に名前ａ2 を付ける。次に、名前
の付いたノードで且つ隣接するノードに名前の付いてい
ないノードの１つを着目ノードａs とし（Ｓ４）、ステ
ップＳ２に戻る。図２の場合、名前の付いたノードで且
つ隣接するノードに名前の付いていないノードはＮ２な
ので、ノードＮ２を着目ノードａs としてステップＳ２
に戻る。
【００１７】戻ったステップＳ２では、ノードＮ２に隣
接するノードで名前の無い全てのノードに名前を付け
る。図２の場合、ノードＮ２に隣接するノードで名前の
無いノードはＮ３，Ｎ４なので、それぞれにａ3,ａ4 の
名前を付ける。そして、ステップＳ４において、名前の
付いたノードで且つ隣接するノードに名前の付いていな
いノードの１つを着目ノードａs とし（Ｓ４）、ステッ
プＳ２に戻る。図２の場合、名前の付いたノードで且つ
隣接するノードに名前の付いていないノードはＮ３，Ｎ
４なので、例えばそのうちのノードＮ３を着目ノードａ
s としてステップＳ２に戻る。
接するノードで名前の無い全てのノードに名前を付け
る。図２の場合、ノードＮ２に隣接するノードで名前の
無いノードはＮ３，Ｎ４なので、それぞれにａ3,ａ4 の
名前を付ける。そして、ステップＳ４において、名前の
付いたノードで且つ隣接するノードに名前の付いていな
いノードの１つを着目ノードａs とし（Ｓ４）、ステッ
プＳ２に戻る。図２の場合、名前の付いたノードで且つ
隣接するノードに名前の付いていないノードはＮ３，Ｎ
４なので、例えばそのうちのノードＮ３を着目ノードａ
s としてステップＳ２に戻る。
【００１８】以上のような動作が繰り返され、ステップ
Ｓ３において全てのノードに名前が付与されたと判断さ
れると、ステップＳ５へ進む。図４に図２の各ノードに
付けられた名前を示す。
Ｓ３において全てのノードに名前が付与されたと判断さ
れると、ステップＳ５へ進む。図４に図２の各ノードに
付けられた名前を示す。
【００１９】各ノードの子孫ノード数を算出する処理Ｓ
５〜Ｓ８においては、先ず、付与されたノード名の最大
の添字ｎ（図２の場合は１０）を変数ｔに設定し（Ｓ
５）、名前ａt に隣接し且つｔより大きな添字の名前を
持つノードを全て選び、下記の式により、名前ａt を持
つノードの子孫ノード数ｂt を算出する（Ｓ６）。 ここで、右辺の第１項は名前ａt を持つノードの子ノー
ド数を示し、第２項はそれらの子ノードの子孫ノード数
を示す。
５〜Ｓ８においては、先ず、付与されたノード名の最大
の添字ｎ（図２の場合は１０）を変数ｔに設定し（Ｓ
５）、名前ａt に隣接し且つｔより大きな添字の名前を
持つノードを全て選び、下記の式により、名前ａt を持
つノードの子孫ノード数ｂt を算出する（Ｓ６）。 ここで、右辺の第１項は名前ａt を持つノードの子ノー
ド数を示し、第２項はそれらの子ノードの子孫ノード数
を示す。
【００２０】名前ａt を持つノードの子孫ノード数ｂt
を算出したら、変数ｔを−１して（Ｓ７）、ステップＳ
６の処理を繰り返し、変数ｔが０になった時点で処理を
終了する（Ｓ８）。
を算出したら、変数ｔを−１して（Ｓ７）、ステップＳ
６の処理を繰り返し、変数ｔが０になった時点で処理を
終了する（Ｓ８）。
【００２１】図２の場合、先ず、ノード名ａ10を持つノ
ードＮ１０に隣接し且つ１０より大きな添字の名前を持
つノードを選んで上記式（１）が計算される。この場
合、ノードＮ１０には子ノードは無いので、ノードＮ１
０の子孫ノード数ｂt は０である。次に、ノード名ａ9
を持つノードＮ９について上記式（１）が計算され、右
辺の第１項は１、第２項は０なので、ノードＮ９の子孫
ノード数ｂ9 は１となる。以下、ノードＮ８，Ｎ７，
…，Ｎ１の順にその子孫ノード数が算出される。この結
果は図４に示すものとなる。
ードＮ１０に隣接し且つ１０より大きな添字の名前を持
つノードを選んで上記式（１）が計算される。この場
合、ノードＮ１０には子ノードは無いので、ノードＮ１
０の子孫ノード数ｂt は０である。次に、ノード名ａ9
を持つノードＮ９について上記式（１）が計算され、右
辺の第１項は１、第２項は０なので、ノードＮ９の子孫
ノード数ｂ9 は１となる。以下、ノードＮ８，Ｎ７，
…，Ｎ１の順にその子孫ノード数が算出される。この結
果は図４に示すものとなる。
【００２２】ノード配置部４におけるノード選択手段４
２は、以上のようにして子孫ノード数算出手段４１で算
出された各ノードの子孫ノード数を参照し、その子孫ノ
ード数の多いものから順にＬ個のノードを選択する。例
えば、５個のノードを選択する場合、子孫ノード数の多
いものから順にノードＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５を
選択する。
２は、以上のようにして子孫ノード数算出手段４１で算
出された各ノードの子孫ノード数を参照し、その子孫ノ
ード数の多いものから順にＬ個のノードを選択する。例
えば、５個のノードを選択する場合、子孫ノード数の多
いものから順にノードＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５を
選択する。
【００２３】そして、ノード配置部４におけるノード読
み出し手段４３は、ノード選択手段４２で選択されたノ
ードのデータをディスク装置２から読み出して主記憶３
のデータ部３１に格納し、且つ、主記憶３にデータを読
み出したノードについてはそのポインタを主記憶３上の
データを指し示すように変更した木構造管理情報を主記
憶３の管理部３２に格納する。
み出し手段４３は、ノード選択手段４２で選択されたノ
ードのデータをディスク装置２から読み出して主記憶３
のデータ部３１に格納し、且つ、主記憶３にデータを読
み出したノードについてはそのポインタを主記憶３上の
データを指し示すように変更した木構造管理情報を主記
憶３の管理部３２に格納する。
【００２４】図５は図２に示す木構造データのうち、ノ
ードＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５のデータを主記憶３
のデータ部３１に配置したときの様子を示している。
ードＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５のデータを主記憶３
のデータ部３１に配置したときの様子を示している。
【００２５】図６は処理装置１が行うノード処理の一例
を示すフローチャートである。処理装置１は、例えばノ
ードＮi の属性を知りたい場合、先ず、主記憶３の管理
部３２の木構造管理情報を参照してノードＮi のデータ
の格納先を調べ、主記憶３上にあれば（Ｓ１１でＹＥ
Ｓ）、ノードＮi のデータを主記憶３から読み出して処
理する（Ｓ１３）。例えば、そのデータ中から属性情報
を取得する。また、主記憶３になければ（Ｓ１１でＮ
Ｏ）、ディスク装置２から読み出して同様の処理を行う
（Ｓ１２）。そして、今回処理したノードがルートノー
ドか否かを判別し（Ｓ１４）、ルートノードでなけれ
ば、今回処理したノードＮi よりルートノードに近い隣
接するノードを管理部３２の木構造管理情報から求め、
これを新たなノードＮi とし（Ｓ１５）、ステップＳ１
１に戻って上述した処理を繰り返す。そして、ルートノ
ードまで処理し終えると（Ｓ１４）、今回のノード処理
を終了する。
を示すフローチャートである。処理装置１は、例えばノ
ードＮi の属性を知りたい場合、先ず、主記憶３の管理
部３２の木構造管理情報を参照してノードＮi のデータ
の格納先を調べ、主記憶３上にあれば（Ｓ１１でＹＥ
Ｓ）、ノードＮi のデータを主記憶３から読み出して処
理する（Ｓ１３）。例えば、そのデータ中から属性情報
を取得する。また、主記憶３になければ（Ｓ１１でＮ
Ｏ）、ディスク装置２から読み出して同様の処理を行う
（Ｓ１２）。そして、今回処理したノードがルートノー
ドか否かを判別し（Ｓ１４）、ルートノードでなけれ
ば、今回処理したノードＮi よりルートノードに近い隣
接するノードを管理部３２の木構造管理情報から求め、
これを新たなノードＮi とし（Ｓ１５）、ステップＳ１
１に戻って上述した処理を繰り返す。そして、ルートノ
ードまで処理し終えると（Ｓ１４）、今回のノード処理
を終了する。
【００２６】以上本発明の実施例について説明したが、
本発明は以上の実施例にのみ限定されず、その他各種の
付加変更が可能である。例えば、木構造データをアクセ
スして処理する処理装置１とは別にノード配置部４を設
けたが、処理装置１自体にノード配置部４の機能を取り
込むようにしても良い。また、ノード数が高々１０個の
木構造データを例にしたが、それは説明の便宜上のもの
であり、通常はより多くのノードから構成される木構造
データが対象となるものである。
本発明は以上の実施例にのみ限定されず、その他各種の
付加変更が可能である。例えば、木構造データをアクセ
スして処理する処理装置１とは別にノード配置部４を設
けたが、処理装置１自体にノード配置部４の機能を取り
込むようにしても良い。また、ノード数が高々１０個の
木構造データを例にしたが、それは説明の便宜上のもの
であり、通常はより多くのノードから構成される木構造
データが対象となるものである。
【００２７】
【発明の効果】以上説明したように、本発明は、アクセ
ス速度の高速化を図るために外部記憶装置上のデータの
一部を主記憶上に配置するようにした情報処理装置にお
いて、外部記憶装置に格納された木構造データのノード
のうち子孫ノード数の多いものを優先的に主記憶上に配
置するものであり、アクセス速度向上のために主記憶上
に配置すべき木構造データ部分をデータアクセス時のオ
ーバヘッド無しに決定することができる利点を有する。
ス速度の高速化を図るために外部記憶装置上のデータの
一部を主記憶上に配置するようにした情報処理装置にお
いて、外部記憶装置に格納された木構造データのノード
のうち子孫ノード数の多いものを優先的に主記憶上に配
置するものであり、アクセス速度向上のために主記憶上
に配置すべき木構造データ部分をデータアクセス時のオ
ーバヘッド無しに決定することができる利点を有する。
【図１】本発明の木構造データ格納方式を適用した情報
処理装置の一例を示すブロック図である。
処理装置の一例を示すブロック図である。
【図２】ディスク装置に格納されている木構造データの
例を示す図である。
例を示す図である。
【図３】子孫ノード数算出手段の処理例を示すフローチ
ャートである。
ャートである。
【図４】子孫ノード数算出手段によって図２に示す木構
造データの各ノードに付与された名前と、算出された各
ノードの子孫ノード数とを示す図である。
造データの各ノードに付与された名前と、算出された各
ノードの子孫ノード数とを示す図である。
【図５】木構造データの一部を主記憶に配置した例を示
す図である。
す図である。
【図６】処理装置のノード処理の一例を示すフローチャ
ートである。
ートである。
１…処理装置 ２…ディスク装置 ３…主記憶 ３１…データ部 ３２…管理部 ４…ノード配置部 ４１…子孫ノード数算出手段 ４２…ノード選択手段 ４３…ノード読み出し手段
Claims (3)
- 【請求項１】 アクセス速度の高速化を図るために外部
記憶装置上のデータの一部を主記憶上に配置するように
した情報処理装置において、 前記外部記憶装置に格納された木構造データを対象と
し、そのノードのうち子孫ノード数の多いものを優先的
に前記主記憶上に配置するノード配置部を備えることを
特徴とする木構造データ格納方式。 - 【請求項２】 前記ノード配置部は、前記外部記憶装置
に格納された木構造データの各ノードの子孫ノード数を
算出する子孫ノード数算出手段と、算出された子孫ノー
ド数の多いものから順に所定個数のノードを選択するノ
ード選択手段と、該選択されたノードを前記外部記憶装
置から主記憶上に読み出すノード読み出し手段とを含む
ことを特徴とする請求項１記載の木構造データ格納方
式。 - 【請求項３】 前記ノード読み出し手段は、前記木構造
データの各ノードのデータの格納先情報を含む木構造管
理情報を主記憶上に格納することを特徴とする請求項２
記載の木構造データ格納方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6339243A JP2596397B2 (ja) | 1994-12-29 | 1994-12-29 | 木構造データ格納方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6339243A JP2596397B2 (ja) | 1994-12-29 | 1994-12-29 | 木構造データ格納方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH08185345A JPH08185345A (ja) | 1996-07-16 |
| JP2596397B2 true JP2596397B2 (ja) | 1997-04-02 |
Family
ID=18325616
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6339243A Expired - Lifetime JP2596397B2 (ja) | 1994-12-29 | 1994-12-29 | 木構造データ格納方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2596397B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2006051869A1 (ja) * | 2004-11-12 | 2006-05-18 | Justsystems Corporation | 文書処理装置及び文書処理方法 |
-
1994
- 1994-12-29 JP JP6339243A patent/JP2596397B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH08185345A (ja) | 1996-07-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8250107B2 (en) | Techniques for graph data structure management | |
| CN114840487B (zh) | 分布式文件系统的元数据管理方法和装置 | |
| JP4944160B2 (ja) | 複数のリアルタイム・センサを検索する方法及び装置 | |
| JP2002229825A (ja) | コンピュータメモリ | |
| JP2000057174A (ja) | マルチメディアオブジェクトの格納及び検索のための方法とシステム | |
| CN104426770A (zh) | 路由查找方法及装置、B-Tree树结构的构建方法 | |
| CN109446225A (zh) | 数据缓存方法、装置、计算机设备及存储介质 | |
| KR101411321B1 (ko) | 액티브 노드와 유사한 특성을 가지는 이웃 노드의 관리방법, 장치 및 그 방법을 구현하기 위한 프로그램이 기록된기록매체 | |
| CN115638803A (zh) | 城市兴趣点敏感的个性化路径规划方法 | |
| JPH10240765A (ja) | 類似オブジェクト検索方法および装置 | |
| JPH08185348A (ja) | 情報処理装置および情報処理方法 | |
| JP2596397B2 (ja) | 木構造データ格納方式 | |
| JPH08110912A (ja) | 動画検索装置および動画検索方法 | |
| JP3505393B2 (ja) | 類似オブジェクト検索方法、装置、および類似オブジェクト検索プログラムを記録した記録媒体 | |
| US7159019B2 (en) | Information collection apparatus and method | |
| CN112307272B (zh) | 确定对象之间关系信息的方法、装置、计算设备及存储介质 | |
| CN108270851B (zh) | 一种数据存储方法及装置 | |
| CN115221360A (zh) | 树形结构配置方法和系统 | |
| CN106709045A (zh) | 分布式文件系统中节点选择方法及装置 | |
| JP2560610B2 (ja) | データ処理装置 | |
| JP3460622B2 (ja) | ネットワーク構成データベースの構築および検索方法 | |
| JP2874810B2 (ja) | キーの記憶割り当て方法 | |
| JP5434500B2 (ja) | 木構造処理装置及びプログラム | |
| JPH0456344B2 (ja) | ||
| JPH05108354A (ja) | エキスパートシステム |