JPH03184168A - 二分探索木データ管理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、二分木構造の二分探索木データに対してデー
タの追加、削除、更新等を要求するイベントを処理する
情報処理装置における二分探索木データ管理方式に関す
る。

〔従来の技術〕

従来、高速なデータアクセスが必要なシステムにおいて
は、二分探索木を持つデータ構造が広く使用され、イベ
ントの発生に応答してそのような二分探索木データに対
してデータの追加、削除。

更新等の処理を行っている。そして、二分探索木データ
において特定の部分木だけレベル数が多くなるといった
極端な不平衡状態ができると、そのレベル数の多い箇所
で探索効率が低下するため、従来は、各イベントの処理
時に必要に応じて二分探索木データを平衡な状態に保つ
為の再構成処理を行っている。

第２図は従来の二分探索木データ管理方式の構成図であ
り、ビは計算機等の処理装置、２は磁気ディスク装置等
の外部記憶装置である。外部記憶装置２には二分探索木
データ２１が格納され、処理装置１°には発生したイベ
ントの待ち行列３１を格納する内部記憶部３と、イベン
ト処理および二分探索木データ２１の管理等を行うデー
タ管理部５とが設けられている。このデータ管理部５は
イベント処理手段５１．不平衡状況監視手段５２および
不平衡二分木の再構成手段５３で構成される。

第２図において、発生したイベントは内部記憶部３の待
ち行列３１に一旦格納される。データ管理部５のイベン
ト処理手段５１は、待ち行列３１にイベントが格納され
ている場合には、それを１つ取り出し、この取り出した
イベントに従って外部記憶装置２に格納された二分探索
木データ２１に対しデータの追加、削除、更新等の処理
を行う。

イベント処理手段５１で１つのイベントが処理される毎
に、不平衡状況監視手段５２に制御が渡る。

不平衡状況監視手段５２は今回のイベント処理によって
二分探索木データ２１に不平衡状態が生したか否かを調
べ、不平衡状態が生していなければ制御をイベント処理
手段５１に戻し、イベント処理手段５１は待ち行列３１
に残っている次のイベントを処理する。他方、不平衡状
況監視手段５２が不平衡状態の発生を検出すると、不平
衡二分木の再構成手段５３に制御が渡る。不平衡二分木
の再構成手段５３は二分探索木データ２１が平衡状態を
保つように再構成を行う手段であり、再構成を１テって
二分探索木データ２１を平衡状態に復元すると、制御を
イベント処理手段５１に戻し、イベント処理手段５１は
待ち行列３１に残っている次のイベントを処理する。

〔発明が解決しようとする課題〕

上述した如〈従来の二分探索木データ管理方式において
は、１つのイベント毎に、外部記憶装置内の二分探索木
データに対するデータの追加、削除、更新等のイベント
処理を行うと共に、これによって二分探索木データが不
平衡状態になったか否かを監視し若し不平衡状態になっ
ていれば直ちに平衡状態に保つ再構成処理を行うように
している。このため、イベントの発生頻度が低い場合に
は問題はないが、イベントの発生が輻幀しその頻度が高
くなると、本来側々のイベントにかかるデータ探索の効
率化を狙った再構成処理がネックとなって、イベントの
処理量が発生量に追いつかなくなり、大量の未処理のイ
ベントが滞留して応答時間が悪化する。また、イベント
の待ち行列として大容量のものが必要となり、内部記憶
容量を十分確保できないシステムには適用が困難になる
。

本発明はこのような事情に鑑みて為されたものであり、
その目的は、イベントの処理と再構成処理とを分離し、
再構成処理はそれを行っても支障のない期間中に一括し
て行う構成を採用することにより、単位時間当たりのイ
ベント最大処理量を増大させ、大量の未処理のイベント
が滞留するのを防止した二分探索木データ管理方式を提
供することにある。

〔課題を解決するための手段〕

本発明の二分探索木データ管理方式は、上記の目的を達
成するために、二分木構造の二分探索木データを格納″
する外部記憶装置と、この外部記憶装置に格納された二
分探索木データに対するデータの追加、削除、更新等の
イベントを処理する処理装置とを備えた情報処理装置に
おいて、発生したイベントの待ち行列を格納する内部記
憶手段と、この内部記憶手段の待ち行列からイベントを
逐次取り出し、そのイベントに従って前記外部記憶装置
に格納された二分探索木データに対してデータの追加、
削除、更新等の処理を行うイベント処理手段と、イベン
トの発生頻度を監視する監視手段と、この監視手段によ
って動作可能期間が制御され、動作可能期間においては
、前記外部記憶装置に格納された二分探索木データを平
衡な状態に再ｉＪ？成する再構成処理を行う一括再構成
手段とを有している。

（作用） 本発明の二分探索木データ管理方式においては、外部記
憶装置に格納された二分探索木データに対するデータの
追加、削除、更新等を要求するイベントが発生ずると、
内部記憶手段の待ち行列がその発生したイベントを格納
し、イベント処理手段がその待ち行列からイベントを逐
次取り出し、そのイベントに従って外部記憶装置に格納
された二分探索木データに対してデータの追加、削除、
更新等の処理を行う、このイベント処理手段による処理
とは独立に、監視手段がイベントの発生頻度を監視し、
この監視手段の監視結果によって動作可能期間が制御さ
れる一括再構成手段が、その動作可能期間において外部
記憶装置に格納された二分探索木データを平衡な状態に
再構成する再構成処理を行う。

〔実施例〕

次に、本発明の実施例について図面を参照して詳細に説
明する。

第１図は本発明の一実施例の構成図であり、ｌは計算機
等の処理装置、２は磁気ディスク装置等の外部記憶装置
である。外部記憶装置２には二分探索木データ２１が格
納され、処理装置１には発生したイベントの待ち行列３
１を格納する内部記憶部３と、イベント処理および二分
探索木データ２１の管理等を行うデータ管理部４とが設
けられている。このデータ管理部４はイベント処理手段
４１、　イベント発生監視手段４２．不平衡二分木の一
括再構成手段４３および不平衡状況監視手段４４で構成
されている。ここで、イベント処理手段４１は、待ち行
列３１からイベントを逐次取り出し、そのイベントに従
って二分探索木データ２１に対してデータの追加、削除
、更新等の処理を行う手段、イベント発生監視手段４２
は、発生したイベントを入力してその発生頻度を求める
手段であり、イベントの発生頻度が予め定められた所定
頻度を超えている期間中、不平衡二分木の一括再構成手
段４３に動作停止を指示し、それ以外の期間中は動作開
始を指示する。また、不平衡状況監視手段４４は、外部
記憶装置２に格納された二分探索木データ２１の平衡状
態を常時監視して一括再構成処理の時期が適切であるか
否かを判断する手段であり、予め定められた程度の不平
衡状態を超えると、−括再横戒指示を不平衡二分木の一
括再構成手段４３に出す、不平衡二分木の一括再構成手
段４３は、イベント発生監視手段４２から動作開始が指
示されている期間において、不平衡状況監視手段４４か
ら一括再構成指示が出されると、外部記憶装置２に格納
された二分探索木データ２１の再構成処理を行って、平
衡な状態に復元する処理を行う手段である。

次に、このように構成された本実施例の動作を説明する
。

第１図において、処理装置１で発生したイベントは内部
記憶部３の待ち行列３１に一旦格納される。データ管理
部４のイベント処理手段４１は、待ち行列３１にイベン
トが格納されている場合には、それを１つ取り出し、こ
の取り出したイベントに従って外部記憶装置２に格納さ
れた二分探索木データ２１に対しデータの追加、削除、
更新等の処理を行う、イベント処理手段４１は１つのイ
ベントを処理すると、待ち行列３１にイベントが残存し
ているか否かを調べ、有れば直ちに次のイベントを処理
する。

他方、イベント処理手段４１の動作とは独立に、不平衡
状況監視手段４４が外部記憶装置２に格納された二分探
索木データ２１の平衡状態を監視すると共に、イベント
発生監視手段４２がイベントの発生頻度を監視している
。そして、このイベント発生監視手段４２の監視の結果
、不平衡二分木の一括再構成手段４３を動作させても良
いと判断される期間中は動作開始指示を不平衡二分木の
一括再構成手段４３に出している。不平衡二分木の一括
再構成手段４３は、動作開始指示が出ている期間は、不
平衡状況監視手段４４から一括再構成指示が出される毎
に、外部記憶装置２の二分探索木データ２１に対して再
構成処理を加え、不平衡状態となった二分探索木データ
を平衡状態に復元する。また、監視の結果、不平衡二分
木の一括再構成手段４３を動作させると支障が生しると
判断される期間中は、イベント発生監視手段４２は動作
停止指示を不平衡二分木の−括再構威手段４３に出して
いる。従って、この動作停止指示が出されている期間中
は、イベント処理手段４１によるデータ追加等によって
二分探索木データ２１に不平衡状態が生しても再構成処
理は行われず、この為イベント処理手段４１は連続して
イベント処理を実行することができる。

（発明の効果） 以上説明したように、本発明の二分探索木データ管理方
式においては、イヘントの発生頻度を監視する監視手段
の監視結果によって動作可能期間が制御される一括再構
成手段を設け、イベントの発生頻度が所定頻度以下であ
る期間にのみ一括再構成手段を動作可能として外部記憶
装置に格納された二分探索木データを平衡状態に復元す
るようにし、それ以外の期間では再構成処理を行わずに
データの追加等のイベント処理のみを連続して実行する
ようにしたので、不平衡状態の二分探索木データに対す
るアクセスが起こり得ることにはなるが、それに起因す
る探索効率の低下は少なく、従ってほぼ再構成処理を省
略した分だけイベントの発生頻度が高い状況下での単位
時間当たりのイヘント最大処理量を従来方式に比べて増
大することが可能となり、未処理のイヘントが大量に滞
留するのを防止することができる。

従って、データの追加、削除１更新等にかかるイベント
が断続的に輻較して生し且つ処理の高速化が要求される
にもかかわらずイベントの待ち行列を十分に確保できな
いシステム等に本発明を通用すれば、非常に有効である
。

【図面の簡単な説明】

第１図は本発明の一実施例の構成図および、第２図は従
来例の構成図である。 図において、 ■・・・処理装置 ２・・・外部記憶装置 ３・・・内部記憶部 ４・・・データ管理部 ２１・・・二分探索木データ ３１・・・待ち行列 ４１・・・イベント処理手段 ４２・・・イベント発生監視手段 ４３・・・不平衡二分木の一括再構成手段４４・・・不
平衡状況監視手段

Claims (1)

1. 【特許請求の範囲】 二分木構造の二分探索木データを格納する外部記憶装置
   と、該外部記憶装置に格納された二分探索木データに対
   するデータの追加、削除、更新等のイベントを処理する
   処理装置とを備えた情報処理装置において、 発生したイベントの待ち行列を格納する内部記憶手段と
   、 該内部記憶手段の待ち行列からイベントを逐次取り出し
   、そのイベントに従って前記外部記憶装置に格納された
   二分探索木データに対してデータの追加、削除、更新等
   の処理を行うイベント処理手段と、 イベントの発生頻度を監視する監視手段と、該監視手段
   の監視結果によって動作可能期間が制御され、動作可能
   期間においては、前記外部記憶装置に格納された二分探
   索木データを平衡な状態に再構成する再構成処理を行う
   一括再構成手段とを具備したことを特徴とする二分探索
   木データ管理方式。