(57)【要約】  本発明は、書き込まれたデータを差分データから効率的に読み出すとともに、書き込み状態を過去の任意の時点に戻す。本発明の記憶装置は、データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを格納するリスト記憶手段と、データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を格納するインデックス記憶手段と、を備える。
2015093026.tif 000002
【特許請求の範囲】
【請求項１】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを格納するリスト記憶手段と、
前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を格納するインデックス記憶手段と、を備える書き込み情報記憶装置。
【請求項２】
新たな書き込み要求を取得して、当該新たな書き込み要求に対応する新たな書き込みレコードを前記データリストに追加し、キー値の範囲が、当該新たな書き込み要求の書き込み区間の少なくとも一部と重複するノード（以降、重複ノード）について、キー値の範囲から重複部分を除去し、前記書き込み区間と前記新たな書き込みレコードへのポインタ情報とを含むノードを、ルートノードに最も近い重複ノードの位置に挿入して、前記二分探索木を更新する検索更新手段を、さらに備える請求項１の書き込み情報記憶装置。
【請求項３】
前記検索更新手段は、指定された時点までの書き込みレコードを新しい順に前記データリストから削除し、残った書き込みレコードに基づいて新たな二分探索木を作成する、請求項２の書き込み情報記憶装置。
【請求項４】
前記検索更新手段は、読み出し要求を取得して、キー値の範囲の少なくとも一部が、当該読み出し要求のアドレス範囲に含まれるノードからポイントされる書き込みレコードに含まれるデータ列を出力する、請求項２乃至３の何れかの書き込み情報記憶装置。
【請求項５】
前記検索更新手段は、キー値の範囲全部が前記書き込み区間内に包含されるノードは削除し、キー値の範囲の一部が前記書き込み区間内に包含されるノードについてはキー値の範囲を当該一部以外の範囲に縮小し、前記書き込み区間全部がキー値の範囲に包含されるノードを、キー値の範囲が前記書き込み区間より大きな範囲のノードと小さな範囲のノードの２つのノードに分割することで前記重複部分を除去し、さらに、各ノードの左右のサブツリーの高さの差がたかだか１となるようにノードの位置を入れ替えることにより前記二分探索木の平衡化を行う、請求項２乃至４の何れかの書き込み情報記憶装置。
【請求項６】
前記検索更新手段は、新たな書き込み要求を取得した際に、前記データリスト内の書き込みレコード数が所定数に達していると、新たなデータリストと当該新たなデータリストに対応する新たな二分探索木を作成し、前記データリスト内の書き込みレコードに基づいて前記データ記憶部のデータを更新して、前記二分探索木と前記データリストを削除する、請求項２乃至５の何れかの書き込み情報記憶装置。
【請求項７】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶し、
前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する、方法。
【請求項８】
新たな書き込み要求を取得して、当該新たな書き込み要求に対応する新たな書き込みレコードを前記データリストに追加し、キー値の範囲が、当該新たな書き込み要求の書き込み区間の少なくとも一部と重複するノード（以降、重複ノード）について、キー値の範囲から重複部分を除去し、前記書き込み区間と前記新たな書き込みレコードへのポインタ情報とを含むノードを、ルートノードに最も近い重複ノードの位置に挿入して、前記二分探索木を更新する請求項７の方法。
【請求項９】
指定された時点までの書き込みレコードを新しい順に前記データリストから削除し、残った書き込みレコードに基づいて新たな二分探索木を作成する、請求項８の方法。
【請求項１０】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶する処理と、
前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する処理とをコンピュータに実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、書き込み情報記憶装置、方法、及び、記録媒体に関し、特に、データを格納する記憶装置に対して発行された書き込み要求の情報を蓄積して、そこから更新後のデータを読み出す、書き込み情報記憶装置、方法、及び、記録媒体に関する。
【背景技術】
【０００２】
記憶装置のデータを保護するため、当該記憶装置の参照（読み出し）のみが可能である場合、書き込み処理を必要とするプログラムを実行できない。そのようなプログラムを実行できるようにする為に、他の記憶装置に当該記憶装置のデータとの差分である差分データを保持し、その差分データに対してのみ書き込みを行う方法がある。この方法では、書き込まれたデータの読み出しは、まず差分データから行われ、そこに無ければ保護された記憶装置に保存されたデータが読み出される。【０００３】
非特許文献１は、このような差分データの形式を開示する。この形式は、書き込みにより差分が生じたブロックのビットマップと更新されたブロックデータを保持する。【０００４】
非特許文献２は、ＡＶＬツリー（ＡＶＬ  ｔｒｅｅ、Ａｄｅｌｓｏｎ−Ｖｅｌｓｋｉｉ  ａｎｄ  Ｌａｎｄｉｓ’  ｔｒｅｅ）を開示する。【０００５】
特許文献１は、データを格納する第１ボリュームへの書き込み履歴を記憶する第２ボリュームと、特定時点における第１ボリュームの複製データを記憶する第３ボリュームを備えるストレージ装置を開示する。このストレージ装置は、第２ボリュームに記憶される書き込み履歴を参照して、第３ボリュームに記憶される複製データを、当該特定時点と異なる時点における第１ボリュームの複製データに書き換える。【０００６】
特許文献２の計算機システムは、ファイルシステムの更新履歴を、ファイルシステムとは独立した２次記憶装置に蓄積する。この更新履歴は更新前の内容を格納する。このため、この計算機システムは、過去の所定の時点におけるファイルシステムのイメージを復元することができる。【０００７】
特許文献３の技術のシステムは、修正履歴を用いて、過去の時刻におけるデータを回復する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００８−３３５２７号公報
【特許文献２】特開２００５−５００２４号公報
【特許文献３】特表２００８−５１１０８３号公報
【非特許文献】
【０００９】
【非特許文献１】Ｖｉｒｔｕａｌ  Ｈａｒｄ  Ｄｉｓｋ  Ｉｍａｇｅ  Ｆｏｒｍａｔ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ、  Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ、Ｖｅｒ．１．０、２００６
【非特許文献２】Ｇｅｏｒｇｉｉ  Ｍ．  Ａｄｅｌｓｏｎ−Ｖｅｌｓｋｉｉ  ａｎｄ  Ｅｖｇｅｎｉｉ  Ｍ．  Ｌａｎｄｉｓ、  Ａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  ｏｒｇａｎｉｚａｔｉｏｎ  ｏｆ  ｉｎｆｏｒｍａｔｉｏｎ、  Ｄｏｋｌａｄｙ  Ａｋａｄｅｍｉｉ  Ｎａｕｋ  ＳＳＳＲ、  １４６：２６３−２６６、  １９６２  （Ｒｕｓｓｉａｎ）．  （Ｅｎｇｌｉｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｂｙ  Ｍｙｒｏｎ  Ｊ．  Ｒｉｃｃｉ  ｉｎ  Ｓｏｖｉｅｔ  Ｍａｔｈ．  Ｄｏｋｌａｄｙ、  ３：１２５９−１２６３、  １９６２．）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述した方法を用いたシステムでは、書き込まれたデータを差分データから効率的に読み出すとともに、書き込み状態を過去の任意の時点に戻すことが課題となる。【００１１】
非特許文献１の形式の差分データを使用したシステムは、重複するアドレス区間への書き込みがあると、差分データを上書きする。したがって、このシステムは、書き込み状態を過去の任意の時点に戻すことができない。【００１２】
特許文献１のシステムは、書き込み履歴データは第３ボリュームのデータ更新に用いられるだけであり、書き込み履歴データから、最新の書き込みデータを読み出すものではない。特許文献２および３の技術も同様である。【００１３】
本発明は、上記課題を解決する、書き込み情報記憶装置、方法、及び、記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一実施形態にかかる書き込み情報記憶装置は、データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを格納するリスト記憶手段と、前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を格納するインデックス記憶手段と、を備える。【００１５】
本発明の一実施形態にかかる方法は、データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶し、前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する。
【発明の効果】
【００１６】
本発明にかかる装置は、更新後のデータを、差分データから効率的に読み出すことができるとともに、書き込み状態を過去の任意の時点に戻すことができる。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明の第１の実施形態にかかる書き込み情報記憶装置１の構成図である。
【図２】図２は、データリスト２２１のデータ構造を示す図である。
【図３】図３は、平衡二分探索木１１１を構成する各ノード１１２のデータ構造を示す図である。
【図４】図４は、書き込み要求のシーケンス例に対して作成されるデータリスト２２１と平衡二分探索木１１１の構成方法の一例を示す図である。
【図５】図５は、データ記憶部２１が書き込み禁止のときに、書き込み要求を受信した探索更新部３３の動作フローチャートである。
【図６Ａ】図６Aは、探索更新部３３が、重複ノードについて、キー値の範囲から重複部分を除去する過程を示す図である（ケース１−Ａ）。
【図６Ｂ】図６Bは、探索更新部３３が、キー値の範囲を短縮し、新たなノードを最上位重複ノードの位置に挿入する過程を示す図である（ケース１−Ｂ）。
【図６Ｃ】図６Cは、探索更新部３３が、ノードを回転する過程を示す図である（ケース１−Ｃ）。
【図７Ａ】図７Aは、探索更新部３３が、重複ノードについて、キー値の範囲から重複部分を除去する過程を示す図である。
【図７Ｂ】図７Bは、探索更新部３３が、分割されたノードをサブツリーに挿入する過程を示す図である。
【図８】図８は、第２の実施の形態の書き込み情報記憶装置１の構成図である。
【図９】図９は、第３の実施の形態の書き込み情報記憶装置１の構成図である。
【発明を実施するための形態】
【００１８】
＜第１の実施の形態＞
図１は、本発明の第１の実施形態にかかる書き込み情報記憶装置１の構成図である。
【００１９】
書き込み情報記憶装置１は、例えば、コンピュータである。書き込み情報記憶装置１は、アプリケーションプログラム３１と、データ記憶部２１に記憶されているデータの読み書きを行うファイルシステム３２とを、プロセッサ３０で実行する。また、書き込み情報記憶装置１は、探索更新部３３と、リスト記憶部２２と、インデックス記憶部１１とを備える。
【００２０】
探索更新部３３は、ファイルシステム３２から命令を受信して、データ記憶部２１のデータの読み書きを行う。しかし、データ記憶部２１は、一時的に書き込みが禁止されて、読み出しのみ許されることがある。このような禁止は、例えば、データ記憶部２１のバックアップデータをバックアップディスク装置（図示されない）等に格納するバックアッププログラム（図示されない）によってなされる。バックアッププログラムは、書き込み情報記憶装置１で実行されるかもしれないし、データ記憶部２１を共有する他のコンピュータ（図示されない）により実行されるかもしれない。
【００２１】
書き込みが禁止されている期間に、ファイルシステム３２から書き込みが要求された場合、探索更新部３３は、書き込みデータを含む書き込み要求を、リスト記憶部２２にデータリスト２２１として記憶しておく。探索更新部３３は、書き込み禁止が解除されてから、データリスト２２１の内容に基づいて、データ記憶部２１内のデータを更新（ロールフォーワードを実行）する。
【００２２】
書き込みが禁止されている期間に、ファイルシステム３２から読み出しが要求された場合、探索更新部３３は、読み出し範囲のデータがデータリスト２２１内に記憶されていればそこから、記憶されていなければデータ記憶部２１から読み出す。読み出し範囲に何回も書き込みがなされた場合、当該範囲のデータがデータリスト２２１内に何世代も記憶される。この場合、探索更新部３３は、読み出し範囲のアドレスごとに最新のデータを読み出す。データリスト２２１から最新データを読み出す速度を向上させるため、探索更新部３３は、データリスト２２１に対応したインデックスをインデックス記憶部１１に作成する。このインデックスは、平衡二分探索木１１１である。
【００２３】
なお、ファイルシステム３２が探索更新部３３に書き込み命令を発行するときは、データ記憶部２１の中の記憶領域のアドレス範囲とデータ列を指定する。ファイルシステム３２が読み出し命令を発行するとき、データ記憶部２１の中の記憶領域のアドレス範囲を指定する。なお、アドレス範囲は、例えば、開始アドレスと終了アドレス、または、開始アドレスとデータ長である。
【００２４】
探索更新部３３は論理回路で構成される。探索更新部３３は、プロセッサ３０とは別のマイクロプロセッサを中心とした論理回路でもよい。さらに、探索更新部３３は、書き込み情報記憶装置１のメモリに格納されて、プロセッサ３０で実行されるプログラムによって実現されても良い。データ記憶部２１およびリスト記憶部２２は、例えば、ディスク装置である。インデックス記憶部１１は、ＩＣメモリ（Integrated Circuit）またはディスク装置である。
【００２５】
図２は、データリスト２２１のデータ構造を示す図である。データリスト２２１は、書き込み要求ごとに、そのアドレス範囲とデータ列を含む書き込みレコードを格納する。書き込みレコードは、例えば、書き込み時刻の順に格納される。書き込みレコードが書き込み時刻を包含し、その値により、探索更新部３３が書き込みレコードの時系列を判断しても良い。
【００２６】
図３は、平衡二分探索木１１１を構成する各ノード１１２のデータ構造を示す図である。各ノード１１２は、アドレスの範囲、当該アドレスの範囲の最新データを含むデータリスト２２１内の書き込みレコードまたは書き込みレコード内の文字列へのポインタ（例えば、データリスト２２１のファイル先頭からのオフセット）、サブツリーの左右の下位のノード１１２（以降、子ノード）へのポインタを包含する。平衡二分探索木１１１は、アドレスをキーとして検索される。この意味で、ノード１１２のアドレス範囲を、キー値の範囲と呼ぶことがある。
【００２７】
平衡二分探索木１１１はＡＶＬツリー（非特許文献２参照）である。平衡二分探索木１１１は、左右のそれぞれのサブツリーの高さの差が多くとも１である。
【００２８】
探索更新部３３は、ＡＶＬツリーのキー値の大小関係を判別する必要がある。その為、重複や包含関係があり得る書き込み要求のアドレス範囲（以降、書き込み区間）をそのままキー値とすることはできない。したがって、探索更新部３３は、平衡二分探索木１１１を更新する際に、ノード１１２間のキー値の範囲の重複を排除する。こうすることで、探索更新部３３は、特定のアドレスを検索キーとして、当該検索キーを含む区間またはその前後の区間のノード１１２を検索することができる。
【００２９】
探索更新部３３は、ノード１１２のうちのルートノードから始めて、ノード１１２のキー値の範囲が検索キーより大きいアドレスの区間なら右の子ノード、検索キーより小さいアドレスの区間なら左の子ノードを辿ることができる。このように探索更新部３３は、その特定のアドレスを含む区間、またはその前後の区間に対応するデータリスト２２１上のデータ列の位置情報を検索することができるのである。
【００３０】
なお、本明細書において、便宜上、親ノードのキー値の範囲より小さなキー値の範囲の子ノードを左ノード、親ノードのキー値の範囲より大きなキー値の範囲の子ノードを右ノードと呼ぶが、呼称とキー値の大小関係はこの例に限られない。
【００３１】
図４は、書き込み要求１００のシーケンス例に対して作成されるデータリスト２２１と平衡二分探索木１１１の構成方法の一例を説明するための図である。
【００３２】
図４の左上は書き込み要求１００のシーケンス例を示す。そのシーケンス例において、横軸はデータ記憶部２１のアドレス、縦軸は時間（時刻ｔ１、t２、ｔ３、ｔ４を含む）を示す。このシーケンス例において、探索更新部３３は、以下の４つの書き込み要求を書き込み要求１００として時系列に受信する。
・時刻ｔ１に、アドレス６乃至１２の領域に文字列“ＡＢＣＤＥＦＧ”
・時刻ｔ２に、アドレス１乃至４の領域に文字列“ＨＩＪＫ”
・時刻ｔ３に、アドレス３乃至１０の領域に文字列“ＬＭＮＯＰＱＲＳ”
・時刻ｔ４に、アドレス５乃至８の領域に文字列“ＴＵＶＷ”
書き込み要求１００は、上述に示す文字列をデータ列として含む。図４の書き込み要求１００を受けたとき、探索更新部３３は、図４の右上に示すデータリスト２２１を作成する。探索更新部３３は、先ず、時刻ｔ１の書き込みに対して、書き込み要求１００の書き込み区間とデータ列を包含する書き込みレコードＲｔ１をデータリスト２２１に格納する。ついで、探索更新部３３は、時刻ｔ２、ｔ３、ｔ４の書き込み要求に対し、順次、書き込みレコードＲｔ２、Ｒｔ３、Ｒｔ４をデータリスト２２１の末尾に追記する。
【００３３】
図４の書き込み要求１００を受けたとき、探索更新部３３は、図４の左下に示すような５つのノード１１２を含む平衡二分探索木１１１を生成する。即ち、各ノード１１２のアドレス範囲に重複、包含関係がなく、ルートノード０の左の子ノードにノード１、その左の子ノードにノード３が配置され、ルートノード０の右の子ノードにノード２、その右の子ノードにノード４が配置される。したがって、探索更新部３３は、アドレスを検索キーとして、平衡二分探索木１１１で最新データを探索できる。平衡二分探索木１１１の各ノードの内容は、次のとおりである。
・ノード３：このノード１１２はキー値の範囲１〜２と書き込みレコードＲｔ２へのポインタを含み、アドレス１乃至２の領域の最新データは、時刻ｔ２の書き込みデータ列“ＨＩ”となることを示す。
・ノード１：このノード１１２はキー値の範囲３〜４と書き込みレコードＲｔ３へのポインタを含み、アドレス３乃至４の領域の最新データは、時刻ｔ３の書き込みデータ列“ＬＭ”となることを示す。
・ノード０：このノード１１２はキー値の範囲５〜８と書き込みレコードＲｔ４へのポインタを含み、アドレス５乃至８の領域の最新データは、時刻ｔ４の書き込みデータ列“ＴＵＶＷ”となることを示す。
・ノード２：このノード１１２はキー値の範囲９〜１０と書き込みレコードＲｔ３へのポインタを含み、アドレス９乃至１０の領域の最新データは、時刻ｔ３の書き込みデータ列“ＲＳ”となることを示す。
・ノード４：このノード１１２はキー値の範囲１１〜１２と書き込みレコードＲｔ１へのポインタを含み、アドレス１１乃至１２の領域の最新データは、時刻ｔ１の書き込みデータ列“ＦＧ”となることを示す。
【００３４】
図５は、データ記憶部２１が書き込み禁止のときに、書き込み要求を受信した探索更新部３３の動作フローチャートである。探索更新部３３は、データリスト２２１と平衡二分探索木１１１の更新を行う。
【００３５】
探索更新部３３は、書き込み区間と書き込みデータ列とを含む新たな書き込みレコードをデータリスト２２１の末尾に追記する（Ｓ１）。次に、探索更新部３３は、新たな書き込みレコードの書き込み区間と新たな書き込みレコードへのポインタ情報を含む新たなノード１１２を作成する（Ｓ２）。
【００３６】
その後、探索更新部３３は重複ノードを探索する（Ｓ３）。ここで、重複ノードとは、キー値の範囲が、書き込み区間の少なくとも一部と重複するノード１１２である。重複ノードが有れば（Ｓ４でＹ）、探索更新部３３は、重複ノードのキー値の範囲から重複する部分を除去し（Ｓ５、Ｓ６、Ｓ１０）、ルートのノード１１２から辿って最初に発見する重複ノード（以降、最上位重複ノード）と同じ位置に、作成した新たなノード１１２を挿入する（Ｓ７）。ノード１１２を同じ位置に挿入するとは、同一の親ノードの同一の子ノードポインタで指し示すようにすることを言う。その後、探索更新部３３は、平衡二分木の再平衡化を行う（Ｓ８）。
【００３７】
さらに詳述すると、重複部分の除去の際、探索更新部３３は、ルートノードから辿って最上位重複ノードを探索し（Ｓ３）、有れば（Ｓ４でＹ）、書き込み区間と当該ノード１１２のキー値の範囲とを比較する（Ｓ５）。
【００３８】
両者が同じ、または、書き込み区間が最上位重複ノードのキー値の範囲より広い場合（Ｓ５でＹ）、探索更新部３３は、キー値の範囲全部が書き込み区間内に包含されるノード１１２を左右のサブツリーから削除する（Ｓ６のａ））。
【００３９】
ここで、図６A乃至図６Cを参照して重複ノードの探索と削除の動作例を説明する。図６Ａは、探索更新部３３が、重複ノードについて、キー値の範囲から重複部分を除去する過程を示す図である。これをケース１−Ａと呼ぶ。図６Ｂは、探索更新部３３が、キー値の範囲を短縮し、新たなノードを最上位重複ノードの位置に挿入する過程を示す図である。これをケース１−Ｂと呼ぶ。また、図６Ｃは、探索更新部３３が、ノードを回転する過程を示す図である。これをケース１−Ｃと呼ぶ。
【００４０】
探索更新部３３は、例えば、ケース１−Ａにおいて、図６Ａに示す平衡二分探索木１１１の破線内の書き込み区間において、網掛けされたノード１１２（キー値の範囲が書き込み区間と重複するノード）を削除する。さらに、ケース１−Bにおいて、探索更新部３３は、キー値の範囲の一部（二分された一方）が書き込み区間と重複するノード１１２のキー値の範囲を、重複範囲以外の範囲（二分された他方）に短縮する（Ｓ６のｂ））。この場合、探索更新部３３は、例えば、図６Ａのノードｘとｙのキー値の範囲から、書き込み区間との重複部分を削って、キー値の範囲を短縮する（図６Ｂ）。
【００４１】
探索更新部３３は、作成した新たなノード１１２（図６Bのノードｚ ）を、最上位重複ノードの位置に挿入する（Ｓ７）。例えば、探索更新部３３は、新たなノードｚを最上位重複ノードの位置に挿入する。なお、探索更新部３３は、最上位重複ノードのデータを、新たなノード１１２のデータで更新しても良い。
【００４２】
最後に、図６Cに示すケース１−Cのように、探索更新部３３は、ノード１１２の回転による再平衡化を行う（Ｓ８）。具体的に、探索更新部３３は、ノードｘを回転して、左右のサブツリーの高さの差異を、たかだか１とする。なお、回転は２分探索木の周知の操作であるので、詳細な説明は省略する。
【００４３】
探索更新部３３は、上記のＳ６、Ｓ７の処理を次の様に実行しても良い。
【００４４】
探索更新部３３は、まず、ルートのノード１１２から辿って最上位重複ノードを発見し、このノード１１２を新たな書き込みの情報で更新し、この書き込みで上書きされる区間のノード１１２を左右のサブツリーから削除する。
【００４５】
このとき、探索更新部３３は、右のサブツリーに対して、書き込み区間の終了位置のアドレスを検索キーとして、ノード１１２のキー値が検索キーより大きいアドレスの区間なら左の子ノードを辿り、検索キーより小さいアドレスの区間ならそのノード１１２と左のサブツリーを一括削除する。この時、探索更新部３３は、そのノード１１２の右の子ノードが親ノードから新たな子ノードとして辿れるようにポインタを変更する。次に、探索更新部３３は、右の子ノードを辿り、検索キーを含む区間なら検索キーより左の区間を削る形でキー値の区間を短縮する。
【００４６】
子ノードの無いノード１１２（葉ノード）、または、検索キーを含む区間をキー値とするノード１１２に達した後は、探索更新部３３は、辿った経路を戻りながらＡＶＬ木の再平衡化処理をおこなう。即ち、探索更新部３３は、左右のサブツリーの高さの差が２以上ある場合に木構造の回転操作により左右の木の高さの差を縮小する処理を行う。
【００４７】
探索更新部３３は、最上位重複ノードの左のサブツリーも同様に処理する。即ち、探索更新部３３は、書き込み区間の開始位置のアドレスを検索キーとして、ノード１１２のキー値が検索キーより小さいアドレスの区間なら右の子ノードを辿り、検索キーより大きいアドレスの区間ならそのノード１１２と右のサブツリーを一括削除する。この時、探索更新部３３は、そのノード１１２の左の子ノードが親ノードから新たな子ノードとして辿れるようにポインタを変更する。次に、探索更新部３３は、左の子ノードを辿り、検索キーを含む区間なら検索キーより右の区間を削る形でキー値の区間を短縮する。
【００４８】
その後、探索更新部３３は、葉ノード、または、検索キーを含む区間をキー値とするノード１１２に達した後は辿った経路を遡って再平衡化処理を行う。
【００４９】
一方、上述のＳ５の判定が偽であって（Ｓ５でＮ）、かつ、書き込み区間が最上位重複ノードのキー値の範囲より狭い場合、探索更新部３３は、当該ノード１１２を、キー値の範囲が、書き込み区間より大きな範囲のノード１１２と小さな範囲のノード１１２に分割する（Ｓ１０のａ））。探索更新部３３は、例えば、図７Ａに示す網掛けされたノード１１２を、書き込み区間（図７Aの破線内の区間 ）よりキー値が小さな区間のノードｐと書き込み区間よりもキー値が大きな区間のノードｑに分割する。
【００５０】
次に、探索更新部３３は、キー値が大きな範囲のノードを右のサブツリーに、キー値が小さな範囲のノード１１２を左のサブツリーに追加する（Ｓ１０のｂ））。探索更新部３３は、例えば、図７Ｂのように、書き込み区間よりキー値が小さな区間のノードｐを左のサブツリーに、書き込み区間よりキー値が大きな区間のノードｑを右のサブツリーに挿入する。ここで、挿入するノードｐおよびノードｑのキー値となる区間は、サブツリー内の区間と重複しない。したがって、探索更新部３３は、通常のＡＶＬ木の挿入処理と同様にノートｐおよびノードｑを挿入することができる。
【００５１】
探索更新部３３は、作成した新たなノード１１２を、最上位重複ノードの位置に挿入する（Ｓ７）。例えば、探索更新部３３は、新たなノードｒを最上位重複ノードの位置に挿入する。なお、探索更新部３３は、最上位重複ノードのデータを、新たなノード１１２のデータで更新しても良い。
【００５２】
その後、探索更新部３３は、ルートのノード１１２から最上位重複ノードまで辿った経路も遡って再平衡化処理を行う（Ｓ８）。
【００５３】
なお、上述のＳ５の判定が偽であって（Ｓ５でＮ）、かつ、書き込み区間が最上位重複ノードのキー値の範囲とずれて重なっている場合、探索更新部３３は以下の処理を行う（図５に図示されず）。先ず、ａ）書き込み区間と最上位重複ノードのキー値の範囲が重なっている部分、および、ｂ）書き込み区間が最上位重複ノードのキー値の範囲を超える（最上位重複ノードのキー値よりも大きい、または、小さい）部分について、探索更新部３３はＳ６に記載した処理を行う。さらに、ｃ）最上位重複ノードのキー値の範囲が書き込み区間のキー値の範囲を超える（書き込み区間のキー値よりも大きい、または、小さい）部分について、探索更新部３３は、当該区間のノード１１２、例えば、キー値の範囲が短縮された後の最上位重複ノード、を右または左のサブツリーに追加する。
【００５４】
なお、重複ノードが無い場合（Ｓ４でＮ）、探索更新部３３は、新たなノード１１２を、書き込み区間に応じた位置に挿入する（Ｓ１１）。ここで、挿入するノード１１２のキー値となる区間は、平衡二分探索木１１１内の区間と重複しない。したがって、探索更新部３３は、通常のＡＶＬ木の挿入処理と同様に当該ノード１１２を挿入することができる。
【００５５】
アプリケーションプログラム３１からファイルシステム３２を介してデータの読み出しが要求されると、探索更新部３３は、指定されたアドレスの範囲（以降、読み出し区間）の開始アドレスをキーに、平衡二分探索木１１１から、開始アドレスがキー値の範囲に包含されるノード１１２を検索する。当該ノード１１２を発見した場合、探索更新部３３は当該ノード１１２のポインタが示すデータリスト２２１の書き込みレコードから、当該ノード１１２のキー値の範囲と読み出し区間の重複する区間対応のデータを読み出す。
【００５６】
以降、探索更新部３３は、読み出し区間の終了アドレスまでアドレス順に書き込みデータ列を読み出す。なお、探索更新部３３は、読み出し区間のうち、データリスト２２１上のデータ列がない区間については、データ記憶部２１からデータを読み出す。
【００５７】
最後に、探索更新部３３は、データリスト２２１またはデータ記憶部２１から読み出したデータ列を結合して、読み出し区間のデータ列を生成し、読み出し結果としてファイルシステム３２を介してアプリケーションプログラム３１に返却する。
【００５８】
書き込み状態を過去の或る時刻に戻すとき、探索更新部３３はインデックス記憶部１１上の平衡二分探索木１１１を初期化する。その後、探索更新部３３は、データリスト２２１から不要な書き込みの書き込みレコードを削除する。ここで、不要な書き込みとは、上記或る時刻以降に行われた書き込みのコードである。
【００５９】
最後に探索更新部３３は、データリスト２２１の書き込みレコードに基づいて新たな平衡二分探索木１１１を作成する。例えば、探索更新部３３はデータリスト２２１の先頭書き込みレコード（書き込み時刻の最も古い書き込みレコード）から順に、書き込みレコードのアドレスの範囲と書き込みデータ列の位置情報を平衡二分探索木１１１に再挿入する。
【００６０】
本実施の形態の書き込み情報記憶装置１は、データ記憶部２１のデータを保全しつつ、データリスト２２１の差分データから最新データを効率よく読み出すことが可能である。その理由は、探索更新部３３がデータ検索用に平衡二分探索木１１１を作成して使用するからである。
【００６１】
データリスト２２１に記録された書き込みレコードの件数ｎに対して平衡二分探索木１１１のノード数は最大で２ｎ−１となり、木の高さはlog２(２n-１)以下となる。したがって、検索処理は最悪でもノード数の対数のオーダで実施でき、読み出し処理の所要時間が、書き込みレコード件数の増加に比例して増加することがない。
【００６２】
さらに、本実施の形態の書き込み情報記憶装置１は、データリスト２２１に記録されている範囲で、書き込み状態を任意の書き込みが行われる前の状態に戻すことができる。その理由は、データリスト２２１は、書き込み要求ごとの書き込みレコードを、書き込み順が分かるように記憶しているからである。
【００６３】
本実施の形態の書き込み情報記憶装置１は、複数の重複ノードの削除を伴う平衡二分探索木１１１の更新処理も効率的に実施できる。通常のＡＶＬ木の削除処理であれば削除するノード１１２の数に比例した所要時間を要する。本実施形態の探索更新部３３は、重複ノードを検索しながらサブツリー単位で削除する為、ノード１１２の数の対数のオーダで実施できる。その為、本実施の形態の書き込み情報記憶装置１においては、書き込み処理の所要時間も、書き込みレコード件数の増加に比例して増加することがない。
【００６４】
＜第２の実施の形態＞
図８は、本実施の形態の書き込み情報記憶装置１の構成図である。本実施の形態のデータ記憶部２１は複数のデータリスト２２１を記憶する。リスト記憶部２２は、各々のデータリスト２２１に対応する平衡二分探索木１１１を記憶する。
【００６５】
第１の実施の形態では、データリスト２２１は、無制限に書き込みのレコードを追記する。平衡二分探索木１１１によって、インデックスの検索と更新の所要時間を書き込みレコード件数の対数のオーダに抑えても、書き込みレコード件数が無制限に増加すると平衡二分探索木１１１の操作の所要時間が無視できなくなる。
【００６６】
この問題に対し、データリスト２２１に記録する書き込みレコード数に上限を設け、書き込み単位でのデータ回復が可能なのはこの上限までとし、それ以前の古い書き込みはデータ記憶部２１に反映してデータリスト２２１から削除する、という対処を行っても良い。しかし、古い書き込みデータをデータリスト２２１から削除する都度、平衡二分探索木１１１を再編するのは効率が悪い。
【００６７】
そこで、本実施の形態の書き込み情報記憶装置１は、探索更新部３３が複数のデータリスト２２１、各データリスト２２１に対応する複数の平衡二分探索木１１１を持つ。探索更新部３３は、データリスト２２１の書き込みレコード件数が上限に達すると、書き込みレコードの追記先を新たなデータリスト２２１に切り替え、古いデータリスト２２１の内容を一括でデータ記憶部２１に反映する。こうすることで、探索更新部３３は、平衡二分探索木１１１の再編を行わずにデータ記憶部２１に古い書き込みを反映する。
【００６８】
データの読み出し時、探索更新部３３は、まず書き込みレコードを追記中のデータリスト２２１から書き込みデータ列を検索して読み出す。探索更新部３３は、そこにデータの無い区間は一つ前の（１世代古い）データリスト２２１から検索して読み出し、そこにも無ければさらに一つ前、と複数のデータリスト２２１を新しいものから順に検索する。いずれのデータリスト２２１にも無ければ、探索更新部３３は、データをデータ記憶部２１から読み出す。
【００６９】
探索更新部３３は、古いデータリスト２２１を、最新データリスト２２１の検索・更新処理のバックグラウンドで、データ記憶部２１へ反映する。探索更新部３３は、反映が完了した後、そのデータリスト２２１とそのデータリスト２２１に対応する平衡二分探索木１１１を削除する。これにより、探索更新部３３は、古いデータリスト２２１の反映中も書き込みや読み出しを継続することができる。
【００７０】
書き込み状態を過去の或る時刻に戻すとき、探索更新部３３は、不要な書き込みレコードをデータリスト２２１から削除し、そのデータリスト２２１の平衡二分探索木１１１のみ初期化・再編する。これにより、データ記憶部２１への反映を行っていないデータリスト２２１に記録された範囲で、書き込み状態を任意の書き込みが行われる前の状態に戻すことができる。
【００７１】
本実施の形態の書き込み情報記憶装置１は、データ記憶部２１の書き込みが禁止されている期間に、多数の書き込みが有っても効率よく、平衡二分探索木１１１の検索、更新が可能である。その理由は、本実施の形態の書き込み情報記憶装置１は、複数のデータリスト２２１と平衡二分探索木１１１を備えるからである。
【００７２】
＜第３の実施の形態＞
図９は、本実施の形態の書き込み情報記憶装置１の構成図である。本実施の形態の書き込み情報記憶装置１は、インデックス記憶部１１とリスト記憶部２２を備える。
【００７３】
リスト記憶部２２は、データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録する。インデックス記憶部１１は、データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノード（たとえば、図３に示すノード１１２）の二分探索木を格納する。
【００７４】
本実施の形態において、書き込み情報記憶装置１はコンピュータでもよいし、データベースを記憶する可換記憶媒体でもよい。書き込み情報記憶装置１がデータベースを記憶する可換媒体、例えば、磁気テープ媒体である場合、当該磁気テープ媒体がコンピュータ装置の磁気テープドライブ装置に装着されて、データベースがコンピュータにインストールされる。
【００７５】
本実施の形態の書き込み情報記憶装置１は、データ記憶部のデータを保全しつつ、リスト記録部２２に記録されるデータリストの差分データから最新データを効率よく読み出すことが可能である。その理由は、データ検索用に二分探索木を備えるからである。
【００７６】
以上、上述した実施形態を模範的な例として本発明を説明した。しかしながら、本発明は、上述した実施形態には限定されない。即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【００７７】
この出願は、２０１３年１２月１７日に出願された日本出願特願２０１３−２６０１３２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７８】
１    書き込み情報記憶装置
１１    インデックス記憶部
１１１    平衡二分探索木
１１２    ノード
２１    データ記憶部
２２    リスト記憶部
２２１    データリスト
３０    プロセッサ
３１    アプリケーションプログラム
３３    探索更新部
【図１】
2015093026.tif 000003
【図２】
2015093026.tif 000004
【図３】
2015093026.tif 000005
【図４】
2015093026.tif 000006
【図５】
2015093026.tif 000007
【図６Ａ】
2015093026.tif 000008
【図６Ｂ】
2015093026.tif 000009
【図６Ｃ】
2015093026.tif 000010
【図７Ａ】
2015093026.tif 000011
【図７Ｂ】
2015093026.tif 000012
【図８】
2015093026.tif 000013
【図９】
2015093026.tif 000014
【手続補正書】
【提出日】平成27年5月12日(2015.5.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを格納するリスト記憶手段と、
前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探素木を格納するインデックス記憶手段と、を備えるコンピュータである書き込み情報記憶装置。
【請求項２】
新たな書き込み要求を取得して、当該新たな書き込み要求に対応する新たな書き込みレコードを前記データリストに追加し、キー値の範囲が、当該新たな書き込み要求の書き込み区間の少なくとも一部と重複するノード（以降、重複ノード）について、キー値の範囲から重複部分を除去し、前記書き込み区間と前記新たな書き込みレコードへのポインタ情報とを含むノードを、ルートノードに最も近い重複ノードの位置に挿入して、前記二分探索木を更新する検索更新手段を、さらに備える請求項１の書き込み情報記憶装置。
【請求項３】
前記検索更新手段は、指定された時点までの書き込みレコードを新しい順に前記データリストから削除し、残った書き込みレコードに基づいて新たな二分探索木を作成する、請求項２の書き込み情報記憶装置。
【請求項４】
前記検索更新手段は、読み出し要求を取得して、キー値の範囲の少なくとも一部が、当該読み出し要求のアドレス範囲に含まれるノードからポイントされる書き込みレコードに含まれるデータ列を出力する、請求項２乃至３の何れかの書き込み情報記憶装置。
【請求項５】
前記検索更新手段は、キー値の範囲全部が前記書き込み区間内に包含されるノードは削除し、キー値の範囲の一部が前記書き込み区間内に包含されるノードについてはキー値の範囲を当該一部以外の範囲に縮小し、前記書き込み区間全部がキー値の範囲に包含されるノードを、キー値の範囲が前記書き込み区間より大きな範囲のノードと小さな範囲のノードの２つのノードに分割することで前記重複部分を除去し、さらに、各ノードの左右のサブツリーの高さの差がたかだか１となるようにノードの位置を入れ替えることにより前記二分探索木の平衡化を行う、請求項２乃至４の何れかの書き込み情報記憶装置。
【請求項６】
前記検索更新手段は、新たな書き込み要求を取得した際に、前記データリスト内の書き込みレコード数が所定数に達していると、新たなデータリストと当該新たなデータリストに対応する新たな二分探索木を作成し、前記データリスト内の書き込みレコードに基づいて前記データ記憶部のデータを更新して、前記二分探索木と前記データリストを削除する、請求項２乃至５の何れかの書き込み情報記憶装置。
【請求項７】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶し、前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する、方法。
【請求項８】
新たな書き込み要求を取得して、当該新たな書き込み要求に対応する新たな書き込みレコードを前記データリストに追加し、キー値の範囲が、当該新たな書き込み要求の書き込み区間の少なくとも一部と重複するノード（以降、重複ノード）について、キー値の範囲から重複部分を除去し、前記書き込み区間と前記新たな書き込みレコードへのポインタ情報とを含むノードを、ルートノードに最も近い重複ノードの位置に挿入して、前記二分探索木を更新する請求項７の方法。
【請求項９】
指定された時点までの書き込みレコードを新しい順に前記データリストから削除し、残った書き込みレコードに基づいて新たな二分探索木を作成する、請求項８の方法。
【請求項１０】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶する処理と、前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する処理とをコンピュータに実行させるプログラムを記録した記録媒体。
【手続補正書】
【提出日】平成28年5月24日(2016.5.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
データ記憶部に発行された書き込み要求ごとに、書き込み対象のデータ列およびアドレス範囲を含む書き込みレコードを、書き込み要求の時系列が分かるように記録したデータリストを記憶する処理と、前記データ記憶部のアドレス範囲をキー値の範囲として含み、かつ、当該アドレス範囲の最新データを含む書き込みレコードへのポインタ情報を含むノードの二分探索木を記憶する処理とをコンピュータに実行させるプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、書き込み情報記憶装置、方法、及び、プログラムに関し、特に、データを格納する記憶装置に対して発行された書き込み要求の情報を蓄積して、そこから更新後のデータを読み出す、書き込み情報記憶装置、方法、及び、プログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
本発明は、上記課題を解決する、書き込み情報記憶装置、方法、及び、プログラムを提供することを目的とする。
【国際調査報告】
2015093026.tif 000015
2015093026.tif 000016
2015093026.tif 000017
2015093026.tif 000018