(57)【特許請求の範囲】
【請求項１】
データベースにおけるルートノードを変更するように構成された変更装置であって、
ルートノード変更要求を受信するように構成された受信モジュールであって、前記ルートノード変更要求は変更情報を含み、前記データベースはデータ領域と汎用領域とを含み、前記データ領域は前記ルートノードを含み、前記汎用領域は第1のマッピングページ、前記第1のマッピングページの識別子、第2のマッピングページおよび前記第2のマッピングページの識別子を含み、前記第1のマッピングページおよび前記第2のマッピングページの両方が前記ルートノードのマッピングページであり、前記第1のマッピングページおよび前記第2のマッピングページのうちの一方はアクティブ・マッピングページであり、もう一方はスタンバイ・マッピングページであり、前記アクティブ・マッピングページの識別子を変更することによって、前記アクティブ・マッピングページと前記スタンバイ・マッピングページとの間で切替えが実施され、前記アクティブ・マッピングページはデータクエリサービスを処理するために使用される、受信モジュールと、
前記変更情報に従って、前記データベースの前記データ領域内の前記ルートノードを変更するように構成された変更モジュールと、
前記変更されたルートノードを、前記データベースの前記汎用領域に複製するように構成された複製モジュールと、
前記アクティブ・マッピングページの前記識別子が前記第1のマッピングページの前記識別子であることを、前記データベースの前記汎用領域内で発見し、前記第1のマッピングページが前記アクティブ・マッピングページであると決定するように構成された決定モジュールと、
前記汎用領域に複製された前記変更されたルートノードに従って、前記第2のマッピングページを前記変更されたルートノードで置換し、前記アクティブ・マッピングページの前記識別子を前記第2のマッピングページの前記識別子に変更するように構成された置換モジュールと
を含む変更装置。
【請求項２】
前記置換モジュールは、前記アクティブ・マッピングページの前記識別子が前記第2のマッピングページの前記識別子に変更された後で、且つ、前記第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、現在の第1のマッピングページを前記変更されたルートノードで置換するようにさらに構成される、請求項1に記載の変更装置。
【請求項３】
データクエリ要求を受信し、前記アクティブ・マッピングページの前記識別子が前記第2のマッピングページの前記識別子であることを発見し、前記データクエリ要求を前記第2のマッピングページに送信するように構成され、その結果、前記第2のマッピングページは前記データクエリ要求を処理する、クエリモジュールをさらに含む、請求項1または2に記載の変更装置。
【請求項４】
前記ルートノード変更要求が受信された後、前記ルートノードに対して排他ロックを設定し、且つ、現在の第2のマッピングページが前記変更されたルートノードで置換された後、前記ルートノードに対する前記排他ロックを解除するように構成されたロック処理モジュールをさらに含む、請求項1乃至3のいずれか1項に記載の変更装置。
【請求項５】
ルートノードを変更するための方法であって、前記方法は、
ルートノード変更要求を受信するステップであって、前記ルートノード変更要求は変更情報を含む、ステップと、
前記変更情報に従って、データベースのデータ領域内のルートノードを変更するステップであって、前記データベースは前記データ領域と汎用領域とを含み、前記データ領域は前記ルートノードを含み、前記汎用領域は第1のマッピングページ、前記第1のマッピングページの識別子、第2のマッピングページおよび前記第2のマッピングページの識別子を含み、前記第1のマッピングページおよび前記第2のマッピングページの両方が前記ルートノードのマッピングページであり、前記第1のマッピングページおよび前記第2のマッピングページのうちの一方はアクティブ・マッピングページであり、もう一方はスタンバイ・マッピングページであり、前記アクティブ・マッピングページの識別子を変更することによって、前記アクティブ・マッピングページと前記スタンバイ・マッピングページとの間で切替えが実施され、前記アクティブ・マッピングページはデータクエリサービスを処理するために使用される、ステップと、
前記変更されたルートノードを、前記データベースの前記汎用領域に複製するステップと、
前記アクティブ・マッピングページの前記識別子が前記第1のマッピングページの前記識別子であることを、前記データベースの前記汎用領域内で発見し、前記第1のマッピングページが前記アクティブ・マッピングページであると決定するステップと、
前記汎用領域に複製された前記変更されたルートノードに従って、前記第2のマッピングページを前記変更されたルートノードで置換し、前記アクティブ・マッピングページの前記識別子を前記第2のマッピングページの前記識別子に変更するステップと
を含む方法。
【請求項６】
前記アクティブ・マッピングページの前記識別子が前記第2のマッピングページの前記識別子に変更された後で、且つ、前記第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、現在の第1のマッピングページは前記変更されたルートノードで置換される、請求項5に記載の方法。
【請求項７】
データクエリ要求を受信し、前記アクティブ・マッピングページの前記識別子が前記第2のマッピングページの前記識別子であることを発見し、前記データクエリ要求を前記第2のマッピングページに送信するステップであって、その結果、前記第2のマッピングページは前記データクエリ要求を処理する、ステップをさらに含む、請求項5または6に記載の方法。
【請求項８】
ルートノード変更要求を受信する前記ステップの後、
前記ルートノードに対して排他ロックを設定するステップ
をさらに含む、請求項5に記載の方法。
【請求項９】
現在の第2のマッピングページを前記変更されたルートノードで置換する前記ステップの後、
前記ルートノードに対する前記排他ロックを解除するステップ
をさらに含む、請求項8に記載の方法。
【請求項１０】
不揮発性のコンピュータ可読記憶媒体であって、前記不揮発性のコンピュータ可読記憶媒体はコンピュータ実行可能プログラムコードを格納するように構成され、且つ、前記プログラムコードは請求項5乃至9のいずれか1項に記載の前記方法を実行するための命令を含む、不揮発性のコンピュータ可読記憶媒体。
【請求項１１】
コンピュータプログラムであって、コンピュータによって実行されるとき、前記コンピュータプログラム内のコードは請求項5乃至9のいずれか1項に記載の前記方法を実施するために使用される、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態はデータベース技術に関し、詳細には、ルートノードを変更するための方法および変更装置に関する。
【背景技術】
【０００２】
従来技術では、インメモリデータベースのデータアクセス速度は一般に、インデックス付け技術を使用することによって改善される。様々なタイプのインデックスがあり、例えば、多分探索木(B*tree)インデックスやハッシュ(Hash)インデックスがある。B*treeにおいては、各ノードは、そのノードに含まれるキーの数、親ノードを指し示すポインタ、キーおよび子ノードを指し示すキーのポインタを含む。ノードが親ノードを持たない場合、すなわち、ノードがルートノードである場合、ノードは親ノードを指し示すポインタを含まず、且つ、ノードが子ノードを持たない場合、すなわち、ノードが葉ノードである場合、葉ノードは葉ノードのキーが指し示す実データを指し示し、子ノードのポインタが指し示す親ノードのキーよりも大きい子ノードのキーはない。
【０００３】
図1はB*treeの典型的な例を示す。最上層にあるノードはルートノードであるとともにクエリの入り口であり、INFは無限大の値である。例えば、我々が28のキーを持つ値についてクエリB*treeを検索する必要がある場合、最初に、28以上の最小のキーについてルートノードが検索され、ここでキーは56であり、次いで、子ノードを指し示すキー56のポインタに従って、キー56の子ノードが発見され、次いで、28以上の最小のキーについて子ノードが検索され、ここでキーは35であり、キー35の子ノードは、子ノードの中に、28のキーを持つ葉ノードを発見するために、子ノードを指し示すキー35のポインタに従ってその後発見される。
【０００４】
数値についてB*treeを検索する前述のプロセスの観点から、クエリが実行されるとき、ルートノードが最初に検索され、条件が満たされる場合、対応するキーの子ノードが検索される。従って、ルートノードは必然的にホットスポットになる。データベースでは、ライトワンス・リードメニー（write-once read-many）並行メカニズムが通常使用され、すなわち、共有ロックが読み出しのために追加され、排他ロックが書き込みのために追加される。このようにして、ルートノードは共有ロックを追加することによって、多くの異なるトランザクションによって読み出されることができ、且つ、ルートノードは排他ロックを追加することによって、1つだけのトランザクションによって書き込まれることができる。
【０００５】
しかしながら、ルートノードが1つだけのトランザクションによって書き込まれるとき、他のトランザクションの読み出し動作は実行されることができない。加えて、全てのクエリ要求はルートノードから開始するため、並行処理効率は非常に低い。
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明の実施形態はルートノードを変更するための方法および変更装置を提供し、その結果、データベースは、クエリ要求を処理するときに変更要求を依然として処理することができる。
【０００７】
第1の態様によると、本発明の実施形態は変更装置を提供し、変更装置はデータベースにおけるルートノードを変更するように構成され、且つ、
ルートノード変更要求を受信するように構成された受信モジュールであって、ここで、ルートノード変更要求は変更情報を含み、データベースはデータ領域と汎用領域とを含み、データ領域はルートノードを含み、汎用領域は第1のマッピングページ、第1のマッピングページの識別子、第2のマッピングページおよび第2のマッピングページの識別子を含み、第1のマッピングページおよび第2のマッピングページの両方がルートノードのマッピングページである、受信モジュールと、
変更情報に従って、データベースのデータ領域内のルートノードを変更するように構成された変更モジュールと、
変更されたルートノードを、データベースの汎用領域に複製するように構成された複製モジュールと、
アクティブ・マッピングページの識別子が第1のマッピングページの識別子であることを、データベースの汎用領域内で発見し、第1のマッピングページがアクティブ・マッピングページであると決定するように構成された決定モジュールと、
汎用領域に複製された変更されたルートノードに従って、第2のマッピングページを変更されたルートノードで置換し、アクティブ・マッピングページの識別子を第2のマッピングページの識別子に変更するように構成された置換モジュールと
を含む。
【０００８】
第1の態様を参照すると、第1の態様の第1の可能な実施方法では、置換モジュールは、アクティブ・マッピングページの識別子が第2のマッピングページの識別子に変更された後で、且つ、第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、現在の第1のマッピングページを変更されたルートノードで置換するようにさらに構成される。
【０００９】
第1の態様を参照すると、第1の態様の第2の可能な実施方法では、前述の変更装置は、データクエリ要求を受信し、アクティブ・マッピングページの識別子が第2のマッピングページの識別子であることを発見し、データクエリ要求を第2のマッピングページに送信するように構成され、その結果、第2のマッピングページはデータクエリ要求を処理する、クエリモジュールをさらに含む。
【００１０】
第1の態様を参照すると、第1の態様の第3の可能な実施方法では、前述の変更装置は、ルートノード変更要求が受信された後、ルートノードに対して排他ロックを設定し、且つ、現在の第2のマッピングページが変更されたルートノードで置換された後、ルートノードに対する排他ロックを解除するように構成されたロック処理モジュールをさらに含む。
【００１１】
第2の態様によると、本発明はルートノードを変更するための方法をさらに提供し、方法は、
ルートノード変更要求を受信するステップであって、ここで、ルートノード変更要求は変更情報を含む、ステップと、
変更情報に従って、データベースのデータ領域内のルートノードを変更するステップであって、ここで、データベースはデータ領域と汎用領域とを含み、データ領域はルートノードを含み、汎用領域は第1のマッピングページ、第1のマッピングページの識別子、第2のマッピングページおよび第2のマッピングページの識別子を含み、第1のマッピングページおよび第2のマッピングページの両方がルートノードのマッピングページである、ステップと、
変更されたルートノードを、データベースの汎用領域に複製するステップと、
アクティブ・マッピングページの識別子が第1のマッピングページの識別子であることを、データベースの汎用領域内で発見し、第1のマッピングページがアクティブ・マッピングページであると決定するステップと、
汎用領域に複製された変更されたルートノードに従って、第2のマッピングページを変更されたルートノードで置換し、アクティブ・マッピングページの識別子を第2のマッピングページの識別子に変更するステップと
を含む。
【００１２】
第2の態様を参照すると、第2の態様の第1の可能な実施方法では、アクティブ・マッピングページの識別子が第2のマッピングページの識別子に変更された後で、且つ、第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、現在の第1のマッピングページは変更されたルートノードで置換される。
【００１３】
第2の態様を参照すると、第2の態様の第2の可能な実施方法では、前述の方法は、データクエリ要求を受信し、アクティブ・マッピングページの識別子が第2のマッピングページの識別子であることを発見し、データクエリ要求を第2のマッピングページに送信するステップであって、その結果、第2のマッピングページはデータクエリ要求を処理する、ステップをさらに含む。
【００１４】
第2の態様を参照すると、第2の態様の第3の可能な実施方法では、前述の方法は、ルートノード変更要求が受信された後、ルートノードに対して排他ロックを設定するステップをさらに含み、且つ、現在の第2のマッピングページが変更されたルートノードで置換された後、ルートノードに対する排他ロックを解除するステップをさらに含む。
【００１５】
第3の態様によると、本発明は不揮発性のコンピュータ可読記憶媒体をさらに提供し、ここで、不揮発性のコンピュータ可読記憶媒体はコンピュータ実行可能プログラムコードを格納するように構成され、且つ、プログラムコードは第2の態様および第2の態様の第1乃至第3の可能な実施方法のいずれか1つによる方法を実行するための命令を含む。
【００１６】
第4の態様によると、本発明はコンピュータプログラムをさらに提供し、ここで、コンピュータによって実行されるとき、コンピュータプログラム内のコードは第2の態様および第2の態様の第1乃至第3の可能な実施方法のいずれか1つによる方法を実施するために使用される。
【００１７】
本発明の実施形態では、ルートノードに対応する第1のマッピングページおよび第2のマッピングページが汎用領域に格納され、ここで、マッピングページの一つはアクティブ・マッピングページとして役目を果たすとともにデータアクセスサービスを処理するために使用される。従って、ルートノードが変更された後、ルートノードに対してロックを追加する必要はなく、且つ、アクセスはアクティブ・マッピングページを使用することによって依然として処理される。加えて、非アクティブ・マッピングページが最初に更新され、次いで、アクティブ・マッピングページの更新を実施するために、非アクティブ・マッピングページはアクティブ・マッピングページに切替えられ、それによって、クエリ要求を処理するときにデータベースは変更要求を依然として処理することができることをさらに実施するとともに、データベースの並行処理効率をさらに改善する。
【図面の簡単な説明】
【００１８】
本発明の実施形態または従来技術における技術的解決手段をより明確に説明するために、以下では、実施形態または従来技術を説明するために必要とされる添付図面を簡潔に導入する。明らかに、以下の説明における添付図面は本発明のいくつかの実施形態を示し、且つ、当業者は創造的努力なしにこれらの添付図面から他の図面をさらに導出することができる。
【００１９】
【図１】図1は従来技術におけるB*treeの概略構成図である。
【図２】図2は本発明の実施形態に係るネットワーク環境の概略図である。
【図３】図3は本発明の実施形態に係る処理装置の概略構成図である。
【図４】図4は本発明の実施形態に係るルートノードを変更するための方法のフローチャートである。
【図５】図5は図1に基づくB*treeを変更した後に得られる概略構成図である。
【図６】図6は本発明の実施形態に係るデータクエリ方法のフローチャートである。
【発明を実施するための形態】
【００２０】
本発明の実施形態の目的、技術的解決手段および利点をより明確にするために、以下では、本発明の実施形態における添付図面を参照して、本発明の実施形態における技術的解決手段を明確かつ完全に説明する。明らかに、説明される実施形態は本発明の実施形態のいくつかであるが全てではない。創造的努力なしに本発明の実施形態に基づいて当業者によって得られる全ての他の実施形態は、本発明の保護範囲に包含するべきである。
【００２１】
図2は本発明の実施形態に係るネットワーク環境の概略図である。アプリケーションプログラム201は、様々な特定の機能を提供することができるコンピュータプログラムを指すとともに、課金アプリケーション、インターネットブラウザ、マルチメディアプレーヤ等を含むが限定はされない。アプリケーションプログラムは、通信ネットワーク202を使用することによってデータベース204にアクセスしてもよく、ここで、データベース204は、具体的には、インメモリデータベース(memory database)であってもよい。複数のアプリケーションプログラムは、汎用領域205またはデータ領域207内のデータにアクセスまたは処理するために、アプリケーションミドルウェア203を使用することによって、データベース204における処理モジュール205と対話してもよい。データベース204は処理モジュール205、汎用領域(general area)206およびデータ領域(data area)207を含む。データ領域207は、本願に関与するルートノード、子ノードおよび特定のデータ等の、特定のデータおよびルートノードを格納する。汎用領域206は、本特許に関与する第1のマッピングページ、第2のマッピングページ、第1のマッピングページの識別子、第2のマッピングページの識別子およびアクティブ・マッピングページの識別子等の、データベースの一時的な管理データを格納し、ここで、第1のマッピングページおよび第2のマッピングページの両方がルートノードのマッピングページであり、同じ時間内に、第1のマッピングページおよび第2のマッピングページのうちの一方はアクティブ・マッピングページであり、もう一方はスタンバイ・マッピングページである。切替えがアクティブ・マッピングページとスタンバイ・マッピングページとの間で実施されてもよい。アクティブ・マッピングページはデータクエリサービスを処理するために使用される。第1のマッピングページおよび第2のマッピングページに含まれるデータはルートノード上に含まれるデータと同じである。従って、アクティブ・マッピングページがデータクエリサービスを処理するとき、従来技術におけるクエリ処理方法が依然として使用される。マッピングページがアクティブ・マッピングページである場合、アクティブ・マッピングページの識別子はマッピングページの識別子である。例えば、第1のマッピングページがアクティブ・マッピングページである場合、アクティブ・マッピングページの現在の識別子は第1のマッピングページの識別子である。第1のマッピングページの識別子、第2のマッピングページの識別子およびアクティブ・マッピングページの識別子は全て数字、文字、記述等であってもよい。例えば、第1のマッピングページの識別子は1であり、第2のマッピングページの識別子は2であり、アクティブ・マッピングページの識別子はmであり、mが1と等しいとき、アクティブ・マッピングページが第1のマッピングページであることを示す。確かに、アクティブ・マッピングページはテキストを使用することによって記述されてもまたよく、例えば、アクティブ・マッピングページの識別子は1である。さらに、インメモリデータベース204はストレージエンジン208にさらに接続される。ストレージエンジン207は永続的なデータを格納する。インメモリデータベース204はデータ領域207内の永続的なデータをストレージエンジン208に格納してもよく、且つ、インメモリデータベース204はストレージエンジン208からデータを取得してもまたよい。さらに、処理モジュール205は、具体的には、変更情報を含むルートノード変更要求を受信し、変更情報に従って、データベースのデータ領域内のルートノードを変更し、変更されたルートノードを、データベースの汎用領域に複製し、アクティブ・マッピングページの識別子が第1のマッピングページの識別子であることを、データベースの汎用領域内で発見し、第1のマッピングページがアクティブ・マッピングページであると決定し、第2のマッピングページを変更されたルートノードで置換し、アクティブ・マッピングページの識別子を第2のマッピングページの識別子に変更するように構成されてもよい。
【００２２】
図3に示されるように、本発明の実施形態は変更装置をさらに提供する。変更装置は、具体的には、図2に示されるデータベース内の処理モジュール206上に配置されてもよい。変更装置は、データベースにおけるルートノードを変更するように構成され、且つ、
ルートノード変更要求を受信するように構成された受信モジュール31であって、ここで、ルートノード変更要求は変更情報を含み、データベースはデータ領域と汎用領域とを含み、データ領域はルートノードを含み、汎用領域は第1のマッピングページ、第1のマッピングページの識別子、第2のマッピングページおよび第2のマッピングページの識別子を含み、第1のマッピングページおよび第2のマッピングページの両方がルートノードのマッピングページである、受信モジュール31と、
変更情報に従って、データベースのデータ領域内のルートノードを変更するように構成された変更モジュール32と、
変更されたルートノードを、データベースの汎用領域に複製するように構成された複製モジュール33と、
アクティブ・マッピングページの識別子が第1のマッピングページの識別子であることを、データベースの汎用領域内で発見し、第1のマッピングページがアクティブ・マッピングページであると決定するように構成された決定モジュール34と、
第2のマッピングページを変更されたルートノードで置換し、アクティブ・マッピングページの識別子を第2のマッピングページの識別子に変更するように構成された置換モジュール35と
を含む。
【００２３】
さらに、置換モジュール35は、アクティブ・マッピングページの識別子が第2のマッピングページの識別子に変更された後で、且つ、第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、現在の第1のマッピングページを変更されたルートノードで置換するようにさらに構成される。
【００２４】
さらに、変更装置はデータを問い合わせるようにさらに構成されてもよい。従って、変更装置は、データクエリ要求を受信し、アクティブ・マッピングページの識別子が第2のマッピングページの識別子であることを発見し、データクエリ要求を第2のマッピングページに送信するように構成され、その結果、第2のマッピングページはデータクエリ要求を処理する、クエリモジュール36をさらに含む。
【００２５】
さらに、変更装置は、ルートノードが変更されているときに、別のトランザクションがルートノードにアクセスする、またはルートノードを変更することを防ぐために、ルートノード変更要求が受信された後、ルートノードに対して排他ロックを設定するように構成され、それによって、ルートノードのデータの一貫性を保証し、且つ、現在の第2のマッピングページが変更されたルートノードで置換された後、ルートノードに対する排他ロックを解除するように構成されたロック処理モジュール37をさらに含む。
【００２６】
図2に示されるネットワーク環境に基づいて、且つ、図3における変更装置に基づいて、図4は本発明に係るルートノードを変更するための方法の実施形態のフローチャートであり、方法は、以下を含む。
【００２７】
ステップ401：ルートノード変更要求を受信し、ここで、ルートノード変更要求は変更情報を含む。
【００２８】
具体的には、アプリケーションプログラムはルートノード変更要求をデータベースの変更装置に送信し、ここで、ルートノード変更要求は変更情報を含み、且つ、変更情報はルートノードの変更されるべきオブジェクトおよび値であってもよい。
【００２９】
確かに、アプリケーションプログラムは、ルートノード変更要求を変更装置に直接送信してもよく、または、ルートノード変更要求を、アプリケーションミドルウェアを使用することによって変更装置に送信してもよい。
【００３０】
ステップ402：変更装置は、変更情報に従って、データベースのデータ領域内のルートノードを変更する。
【００３１】
変更装置がルートノードを変更する必要があるとき、変更装置はルートノードに対して排他ロックを設定する必要があるが、排他ロックはデータクエリに影響を与えず、ルートノードが一度に1つだけのスレッドによって変更されることを保証するだけである。データベースは、ルートノードに対応するマッピングページを使用することによって、データクエリ処理を依然として実行することができる。
【００３２】
ステップ403：変更装置は、変更されたルートノードを、データベースの汎用領域に複製する。
【００３３】
ステップ404：変更装置は、アクティブ・マッピングページの識別子が第1のマッピングページの識別子であることを、データベースの汎用領域内で発見し、第1のマッピングページがアクティブ・マッピングページであると決定する。
【００３４】
ステップ405：第2のマッピングページを変更されたルートノードで置換し、アクティブ・マッピングページの識別子を第2のマッピングページの識別子に変更する。
【００３５】
ステップ404では、第1のマッピングページがアクティブ・マッピングページであることが決定されている。すなわち、第2のマッピングページはアクティブ・マッピングページではない。従って、現在の第2のマッピングページは前述の変更されたルートノードで置換される。このようにして、置換された第2のマッピングページの内容は前述の変更されたルートノードの内容と同じである。さらに、置換された第2のマッピングページは、データ領域内の変更されたルートノードに対応してもよい。従って、第2のマッピングページはアクティブ・マッピングページとなるとともに、データクエリサービスを処理することを開始する。アクティブ・マッピングページが第1のマッピングページであるか第2のマッピングページであるかに関係なく、アクティブ・マッピングページは変更されることはできない。すなわち、アクティブ・マッピングページは読み出し専用である。アクティブ・マッピングページはスタンバイ・マッピングページに切替えられた後にのみ変更されることができる。
【００３６】
アクティブ・マッピングページの識別子が第2のマッピングページの識別子であるとき、すなわち、第1のマッピングページがアクティブ・マッピングページでなく、且つ、第1のマッピングページがデータクエリサービスを処理しないとき、第1のマッピングページによって現在処理されているデータクエリサービスが完了した後、変更装置は、現在の第1のマッピングページを前述の変更されたルートノードで置換する。このようにして、置換された第1のマッピングページの内容は前述の変更されたルートノードと完全に同じであり、且つ、置換された第1のマッピングページはデータ領域内の変更されたルートノードに対応してもよい。
【００３７】
前述の第1のマッピングページおよび第2のマッピングページが成功裏に更新された後、変更装置はルートノードに対する排他ロックを解除する。
【００３８】
具体的には、ルートノードを変更するための前述の方法は、具体的な例を参照して以下に説明される。図1に示されるB*treeのルートノードに子ノードが新たに追加される。図5に示されるように、子ノードを新たに追加するプロセスは以下のようになる。
【００３９】
ノード（説明を簡単にするために、このノードは以下ではオリジナルノードと呼ばれる）がいっぱいになっているとき、このノードの次の兄弟ノードがいっぱいになっていない場合、データの一部は次の兄弟ノードに移され、且つ、キーがオリジナルノードに挿入される。兄弟ノードのキー範囲が変更されるため、親ノードにおける兄弟ノードのキーは最後に変更される。次の兄弟ノードもまたいっぱいになっている場合、オリジナルノードと兄弟ノードとの間に新しいノードが追加され、オリジナルノードおよび兄弟ノードの両方のデータの3分の1が新しいノードに複製され、新しいノードへのポインタが親ノードに最後に追加される。
【００４０】
子ノードを新たに追加する前述のプロセスによると、図1に示されるB*treeに基づくと、新たに追加されたキーは78、80、85、86および89を含み、且つ、図5に示されるB*treeが得られる。ここで、ルートノードを変更するプロセスが導入され、プロセスは以下のようになる。
【００４１】
ルートノードの1つの子ノードが変更され、且つ、1つの子ノードが追加されるため、キー77をルートノードに追加する必要があり、ここで、キーのポインタは65、70および77のキーを持つ子ノードを指し示し、且つ、ルートノードにおけるキーINFのポインタは、85およびINFのキーを持つ子ノードを指し示すように変更される。このようにして、ルートノードは変更される。ルートノードが成功裏に変更された後、汎用領域内の第1のマッピングページおよび第2のマッピングページは、ステップ403乃至405の前述のプロセスに従って変更される。
【００４２】
本発明の実施形態では、ルートノードに対応する第1のマッピングページおよび第2のマッピングページが汎用領域に格納され、ここで、マッピングページの一つはアクティブ・マッピングページとして役目を果たすとともにデータアクセスサービスを処理するために使用される。従って、ルートノードが変更された後、ルートノードに対してロックを追加する必要はなく、且つ、アクセスはアクティブ・マッピングページを使用することによって依然として処理される。加えて、非アクティブ・マッピングページが最初に更新され、次いで、アクティブ・マッピングページの更新を実施するために、非アクティブ・マッピングページはアクティブ・マッピングページに切替えられる。
【００４３】
図6は、本発明に係る、図4におけるルートノードを変更するための方法に基づいて、本発明に係るデータクエリ方法を示す。方法は以下を含む。
【００４４】
ステップ601：アプリケーションプログラムはクエリ要求をデータベースにおける変更装置に送信し、ここで、クエリ要求はクエリキー(key)を含む。
【００４５】
ステップ602：クエリ要求を受信した後、変更装置は、アクティブ・マッピングページの現在の識別子について汎用領域に問い合わせる。例えば、アクティブ・マッピングページの現在の識別子は第2のマッピングページの識別子であり、すなわち、現在の第2のマッピングページはアクティブ・マッピングページである。
【００４６】
ステップ603：変更装置は、前述のキーに従って、第2のマッピングページ上でクエリを実行し、前記キーに対応するとともに第2のマッピングページ上にあるキーを取得し、第2のマッピングページ上の対応するキーに対応するとともに第1の子ノードを指し示すポインタを得る。
【００４７】
確かに、ポインタが特定のアドレスである場合もまた実行可能である。この場合、第1のマッピングページ上の対応するキーに対応するとともに、第1の子ノードを指し示すアドレスが得られてもよい。
【００４８】
ステップ604：第2のマッピングページ上の対応するキーに対応するとともに第1の子ノードを指し示すポインタに従って、第1の子ノードを発見し、第1の子ノードが葉ノードである場合、すなわち、葉ノード上のキーがクエリ要求に含まれるクエリキーである場合、葉ノード上のキーはクエリキーであり、第1の子ノードが葉ノードでない場合、第1の子ノード上でクエリを実行し、クエリキーに対応するとともに第1の子ノード上にあるキーを決定し、第1の子ノード上の対応するキーに対応するとともに第2の子ノードを指し示すポインタを得る。第2の子ノードが葉ノードでない場合、ステップ604は、発見された子ノードが葉ノードであるまで繰り返される。
【００４９】
前述のクエリ要求がキーに対応するデータを問い合せる場合、ステップ605がさらに実行される必要がある。
【００５０】
ステップ605：変更装置は葉ノードのキーに従って、葉ノードのキーに対応する実データを発見する。
【００５１】
図5におけるB*treeを参照して、データクエリプロセスが以下で説明される。図5における85およびINFのキーを持つ子ノードがちょうど新たに追加された後、ルートノードがまだ変更されていないとき、またはルートノードは変更されているが現在のアクティブ・マッピングページが対応して変更されていないとき、変更装置は80のクエリキーを持つクエリ要求を受信するとともに、キー80に従って、現在のアクティブ・マッピングページ上でクエリを実行するとする。現在のアクティブ・マッピングページはキー27、56およびINFのみを持ち、且つ、アクティブ・マッピングページの内容は現在は対応して変更されていないため、ルートノード上で発見される80以上のキーはINFである。キーINFに対応するポインタは、65、70および77のキーを持つ子ノードを指し示すため、65、70および77のキーを持つ子ノードのポインタが取得される。65、70および77のキーを持つノードは子ノードのポインタに従って問い合わされ、且つ、ノード上の最大のキーは77であることが決定される。しかしながら、クエリキーは80であり、且つ、子ノードの葉ノードのキーに80であるものはないことが決定される。従って、ノードの次の兄弟ノードが、65、70および77のキーを持つノード上で問い合わされ、85およびINFのキーを持つノードが兄弟ノードのポインタを使用することによって発見され、80のキーを持つ葉ノードが85およびINFのキーを持つノード上で発見される。
【００５２】
図5における85およびINFのキーを持つ子ノードが新たに追加された後、現在のアクティブ・マッピングページは対応して変更されたとする。次いで、変更装置は80のクエリキーを持つクエリ要求を受信するとともに、キー80に従って、現在のアクティブ・マッピングページ上でクエリを実行する。現在のアクティブ・マッピングページはキー27、56、77およびINFを含むため、ルートノード上で発見される80以上のキーはINFである。キーINFに対応するポインタは85およびINFのキーを持つ子ノードを指し示し、且つ、80のキーを持つ葉ノードが85およびINFのキーを持つノード上で発見される。
【００５３】
本発明の実施形態は、不揮発性のコンピュータ可読記憶媒体をさらに提供し、ここで、不揮発性のコンピュータ可読記憶媒体はコンピュータ実行可能プログラムコードを格納するように構成され、且つ、プログラムコードは図4または図6に対応する実施形態における方法を実行するための命令を含む。
【００５４】
本発明の実施形態はコンピュータプログラムをさらに提供し、ここで、コンピュータによって実行されるとき、コンピュータプログラム内のコードは図4または図6に対応する実施形態における方法を実施するために使用される。
【００５５】
本発明の実施形態では、ルートノードに対応する第1のマッピングページおよび第2のマッピングページが汎用領域に格納され、ここで、マッピングページの一つはアクティブ・マッピングページとして役目を果たすとともにデータアクセスサービスを処理するために使用される。従って、ルートノードが変更された後、ルートノードに対してロックを追加する必要はなく、且つ、アクセスはアクティブ・マッピングページを使用することによって依然として処理される。加えて、非アクティブ・マッピングページが最初に更新され、次いで、アクティブ・マッピングページの更新を実施するために、非アクティブ・マッピングページはアクティブ・マッピングページに切替えられ、それによって、クエリ要求を処理するときにデータベースは変更要求を依然として処理することができることをさらに実施するとともに、データベースの並行処理効率をさらに改善する。
【００５６】
当業者は、方法の実施形態のステップの全てまたはいくつかは、関連するハードウェアに命令するプログラムによって実施されてもよいことを理解することができる。プログラムはコンピュータ可読記憶媒体に格納されてもよい。プログラムが動作するとき、方法の実施形態のステップが実行される。前述の記憶媒体は、ROM、RAM、磁気ディスクまたは光ディスク等のプログラムコードを格納することができる任意の媒体を含む。
【００５７】
最後に、前述の実施形態は単に、本発明の技術的解決手段を説明することを意図されるが、本発明を限定しないことを意図されることは留意されるべきである。本発明は前述の実施形態を参照して詳細に説明されるが、当業者は、本発明の実施形態の技術的解決手段の範囲から逸脱することなく、前述の実施形態で説明される技術的解決手段に変更をさらに行うか、またはそのいくつかの技術的特徴または全ての技術的特徴に同等置換をさらに行なってもよいことは理解するべきである。
【符号の説明】
【００５８】
201  アプリケーションプログラム
202  ネットワーク
203  アプリケーションミドルウェア
204  データベース
205  処理モジュール
206  汎用領域
207  データ領域
31  受信モジュール
32  変更モジュール
33  複製モジュール
34  決定モジュール
35  置換モジュール
36  クエリモジュール
37  ロック処理モジュール
【図１】
0006323887.tif 000002
【図２】
0006323887.tif 000003
【図３】
0006323887.tif 000004
【図４】
0006323887.tif 000005
【図５】
0006323887.tif 000006
【図６】
0006323887.tif 000007