(57)【要約】【課題】新規レコード群が連続的に挿入されるアクセスに対して、複数のデータベース管理装置における負荷を分散すると同時に、各データベース管理装置のBtreeインデックスにおけるランダムなキーの挿入操作回数を削減する。【解決手段】データを記憶装置に格納するデータベース管理装置において、データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成するプレフィックス生成手段と、Btreeインデックスのキーに前記プレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録手段と、Btreeインデックスを検索する際に、検索キーとして合成キーを入力として、Btree インデックスに対する検索を行うインデックス検索手段と、を備える。【選択図】図１
2013242674.tif 000002
【特許請求の範囲】
【請求項１】
データを記憶装置に格納するデータベース管理装置であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成するプレフィックス生成手段と、
Btreeインデックスのキーに前記プレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録手段と、
Btreeインデックスを検索する際に、検索キーとして合成キーを入力として、Btree インデックスに対する検索を行うインデックス検索手段と、
を有するデータベース管理装置。
【請求項２】
データを記憶装置に格納するデータベース管理装置であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成する登録時用のプレフィックス生成手段と、
Btreeインデックスのキーに、前記登録時用のプレフィックス生成手段により生成されたプレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録手段と、
Btreeインデックスを検索する際に、検索キーおよび検索対象の登録者情報を入力として、プレフィックスを生成する検索時用のプレフィックス生成手段と、
前記検索キーに、前記検索時用のプレフィックス生成手段により生成されたプレフィックスを付与した合成キーを用いてBtreeインデックスに対する検索を行うインデックス検索手段と、
を有するデータベース管理装置。
【請求項３】
前記プレフィックス生成手段は、登録される複数レコードにおいて、プレフィックスを付与して得られる合成キーがBtreeインデックスにおいて連続するように、プレフィックスを生成する
請求項１または２に記載のデータベース管理装置。
【請求項４】
前記プレフィックス生成手段は、登録されるレコード群において、インデックスに登録するキーをクラスタ化し、各クラスタにIDを割り当て、得られたクラスタIDをプレフィックスとして生成する
請求項１ないし３のうちいずれか１項に記載のデータベース管理装置。
【請求項５】
データを記憶装置に格納するデータベース管理装置が実行するBtreeインデックス処理方法であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成するプレフィックス生成ステップと、
Btreeインデックスのキーに前記プレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録ステップと、
Btreeインデックスを検索する際に、検索キーとして合成キーを入力として、Btree インデックスに対する検索を行うインデックス検索ステップと、
を有するBtreeインデックス処理方法。
【請求項６】
データを記憶装置に格納するデータベース管理装置が実行するBtreeインデックス処理方法であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成する登録時のプレフィックス生成ステップと、
Btreeインデックスのキーに、前記登録時のプレフィックス生成ステップにより生成されたプレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録ステップと、
Btreeインデックスを検索する際に、検索キーおよび検索対象の登録者情報を入力として、プレフィックスを生成する検索時のプレフィックス生成ステップと、
前記検索キーに、前記検索時のプレフィックス生成ステップにより生成されたプレフィックスを付与した合成キーを用いてBtreeインデックスに対する検索を行うインデックス検索ステップと、
を有するBtreeインデックス処理方法。
【請求項７】
コンピュータを、請求項１ないし４のうちいずれか１項に記載されたデータベース管理装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータベース管理装置を分散構成した分散データベース装置の中で分散方式がハッシュ分散方式である分散データベース装置において、データベース管理装置がBtreeインデックスを利用する方式を対象とした技術に関するものである。
【背景技術】
【０００２】
従来の分散データベース装置では、新規レコードが挿入された際に、まず複数あるデータベース管理装置の中からそのレコードを管理するデータベース管理装置を割り当てる(ルーティングする)。
【０００３】
そして、割り当てられたデータベース管理装置では、挿入されたレコードを格納する際に、インデックス構築を指定されたレコードのキーを用いて、Btreeインデックスにレコードを挿入する。
【０００４】
分散方式がハッシュ分散方式である場合、負荷分散をするためルーティングの際にレコードの特定のカラム値のハッシュ値を利用する。例えば、メールサービスやblog システムのケースでは、利用者IDのハッシュ値を利用することで利用者ごとにデータを分散する例が挙げられる。
【０００５】
また、データベース管理装置におけるBtreeインデックスの性能特性として、ランダムなインデックスのキーの挿入操作はディスク装置においてランダムアクセスが発生して性能が低下するのに対して、シーケンシャルなキーの挿入操作はディスク装置においてシーケンシャルアクセスになるためより性能が高いことが知られている。このことを図７に示している。
【０００６】
上述した従来技術の性能上の特性を踏まえた、分散データベースの設計方針は以下のようになる。
【０００７】
・分散データベース装置全体での性能を負荷分散の観点から向上させるため、各データベース管理装置に挿入されるレコードを均等に割り当てるように、ハッシュに基づいてデータを分散する。
【０００８】
・各データベース管理装置においては、Btreeの性能を向上させるため、シーケンシャルなキーの挿入操作が多くなるように挿入レコードのインデックスキーを設計する。
【０００９】
しかし、ハッシュ分散方式を用いる分散データベース装置においては、上記の2点は両立が難しい。その理由は、一般的に分散の際にハッシュの入力キーをBtree のキーとして利用するため、複数のデータベース管理装置においてレコードが均等に分散されるキーを用いる場合は、各データベース管理装置のBtreeにおいてランダムなインデックスのキーの挿入操作が生じてしまうためである。
【００１０】
例えば、メールサービスやblogシステムのケースにおいて、利用者IDをキーとしてそのハッシュ値によって分散するデータベース管理装置にルーティングを行い、各データベース装置のBtree では利用者IDをキーとする場合、複数の異なる利用者によるレコードの挿入操作によって、ディスク装置においてランダムアクセスが多発してBtreeインデックスの性能が劣化するという問題が生じる。
【００１１】
一方、各データベース管理装置のBtreeにおいてシーケンシャルなインデックスのキーの挿入操作が行われるようなキーを用いる場合は、複数のデータベース管理装置において複数レコードが連続的に同一のデータベース管理装置に割り当てられてしまい、負荷が分散しないという問題が生じてしまう。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Modern B-Tree Techniques, Goetz Graefe (著), 出版社: Now Publishers (2011/08) , ISBN-10: 1601984820 , ISBN-13: 978-1601984821
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は上記の点に鑑みてなされたものであり、新規レコード群が連続的に挿入されるアクセスに対して、複数のデータベース管理装置における負荷を分散すると同時に、各データベース管理装置のBtreeインデックスにおけるランダムなキーの挿入操作回数を削減することで高速なレコード挿入を実現する、ハッシュ分散方式の分散データベース装置におけるデータベース管理装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、本発明は、データを記憶装置に格納するデータベース管理装置であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成するプレフィックス生成手段と、
Btreeインデックスのキーに前記プレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録手段と、
Btreeインデックスを検索する際に、検索キーとして合成キーを入力として、Btree インデックスに対する検索を行うインデックス検索手段と、を有するデータベース管理装置として構成される。
【００１５】
また、本発明は、データを記憶装置に格納するデータベース管理装置であって、
データベースにレコードを登録する際に、登録レコードおよびレコードの登録者情報を入力として、前記データベース管理装置の記憶装置に格納されるBtreeインデックスのキーに付与するプレフィックスを生成する登録時用のプレフィックス生成手段と、
Btreeインデックスのキーに、前記登録時用のプレフィックス生成手段により生成されたプレフィックスを付与した合成キーを用いて登録レコードをBtreeインデックスに登録するインデックス登録手段と、
Btreeインデックスを検索する際に、検索キーおよび検索対象の登録者情報を入力として、プレフィックスを生成する検索時用のプレフィックス生成手段と、
前記検索キーに、前記検索時用のプレフィックス生成手段により生成されたプレフィックスを付与した合成キーを用いてBtreeインデックスに対する検索を行うインデックス検索手段と、を有するデータベース管理装置として構成してもよい。
【００１６】
前記プレフィックス生成手段は、登録される複数レコードにおいて、プレフィックスを付与して得られる合成キーがBtreeインデックスにおいて連続するように、プレフィックスを生成するように構成される。
【００１７】
また、前記プレフィックス生成手段は、登録されるレコード群において、インデックスに登録するキーをクラスタ化し、各クラスタにIDを割り当て、得られたクラスタIDをプレフィックスとして生成するように構成してもよい。
【００１８】
また、本発明は、前記データベース管理装置が実行するBtreeインデックス処理方法として構成してもよく、更に、コンピュータを、前記データベース管理装置における各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１９】
本発明によれば、新規レコード群が連続的に挿入されるアクセスに対して、複数のデータベース管理装置における負荷を分散すると同時に、各データベース管理装置のBtreeインデックスにおけるランダムなキーの挿入操作回数を削減することで高速なレコード挿入を実現する、ハッシュ分散方式の分散データベース装置におけるデータベース管理装置を提供することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態におけるデータベース管理装置１０の構成図である。
【図２】本発明の実施の形態におけるレコード登録操作の制御フローを説明する図である。
【図３】本発明の実施の形態におけるレコード検索操作の制御フローを説明する図である。
【図４】プレフィックス生成手段２１、３１の処理フローを示す図である。
【図５】ツイートデータ管理における第一の具体例を示す図である。
【図６】ツイートデータ管理における第二の具体例を示す図である。
【図７】Btreeインデックスの性能特性を示すグラフである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００２２】
（実施の形態の概要）
まず、本発明の実施の形態の概要について説明する。本実施の形態では、データベース管理装置のBtreeインデックスにおいて、インデックスに挿入する複数レコードに共通する値を算出して、その値をインデックスのキー値にプレフィックスとして付与した合成キーを作成し、合成キーを用いてレコードをインデックス登録する。
【００２３】
この構成により、レコード群が連続して挿入される操作に対して、従来のデータベース管理装置のBtree インデックスよりも、ランダムなキーの挿入操作回数を削減することができる。
【００２４】
Btreeに対する検索を行う際には、検索キーとして合成キーを入力して検索を実行してもよいし、検索キーおよび検索対象の登録者情報を入力として、プレフィックス生成手段によりプレフィックスを得ることで正確なインデックス検索を実現することとしてもよい。
【００２５】
本実施の形態において、上記プレフィックス生成手段では、登録される複数レコードにおいて、プレフィックスを付与して得られる合成キーがBtreeインデックスにおいて連続するように、プレフィックスを生成する。
【００２６】
複数レコードをBtreeインデックスに連続的に登録する際に、このプレフィックスをキーに付与した合成キーを用いてインデックス登録することによって、ランダムなキーの挿入操作回数を削減することができる。
【００２７】
また、上記プレフィックス生成手段は、Btreeインデックスを検索する際には、検索キーおよび検索対象の登録者情報を入力としてプレフィックスを導出し、検索キーにプレフィックスを付与した合成キーを用いることによって、Btreeインデックスに対する検索を正確に行うことができる。
【００２８】
従って、大量のレコード群が挿入されるアクセスに対して、複数のデータベース管理装置における負荷を分散すると同時に、各データベース管理装置のBtreeインデックスにおけるランダムなキーの挿入操作回数を削減することで、高速なレコード挿入を実現することができるようになる。
【００２９】
（実施の形態の詳細）
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
【００３０】
＜装置構成＞
図１に、本実施の形態に係るデータベース管理装置１０の機能構成図を示す。図１に示すように、本実施の形態におけるデータベース管理装置１０は、レコード登録部１１、レコード検索部１２、レコード管理部１３、プレフィックス生成ルール管理部１４を備える。なお、本実施の形態のデータベース管理装置１０は、複数のデータベース管理装置を分散配置した分散データベース装置（システム）を構成する１つのデータベース管理装置である。
【００３１】
データ操作者は分散データベース管理装置を介して、データベース管理装置１０に登録命令または検索命令を入力する。なお、図１では分散データベース管理装置の記載を省略している。
【００３２】
レコード登録部１１は、データ操作者からの登録命令を処理する機能部である。レコード検索部１２は、データ操作者からの検索命令を処理する機能部である。レコード管理部１３は、主記憶およびハードディスク装置に対してレコード群を格納するデータベースおよびレコード群に対して構築したBtreeインデックスを備える。Btreeはレコード群のキーを指定して構築するため、同一のレコード群に対して異なるキーで複数のBtreeインデックスを構築しても良い。
【００３３】
プレフィックス生成ルール管理部１４は、Btreeインデックス毎にプレフィックスをどのように生成するかを定義したルールを保持し、管理する。
【００３４】
本実施の形態に係るデータベース管理装置１０は、ＣＰＵ、メモリ、及びハードディスク等を備えるコンピュータに、各機能部の処理に対応するプログラムを実行させることにより実現可能である。当該プログラムは、可搬メモリ等の記憶媒体に格納して配布し、上記コンピュータにインストールして用いてもよいし、ネットワーク上のサーバからダウンロードして上記コンピュータにインストールしてもよい。
【００３５】
＜装置の詳細構成及び動作＞
以下、本実施の形態に係るデータベース管理装置１０の構成及び動作をより詳細に説明する。
【００３６】
図２を参照して、本実施の形態のデータベース管理装置１０におけるレコード登録操作の制御フローを説明する。図２に示すように、レコード登録部１１は、プレフィックス生成手段２１とインデックス登録手段２２を含む。
【００３７】
まず、クライアントプログラム２０を介して、データ操作者はレコード登録操作をデータベース管理装置１０に入力する（ステップ２１）。
【００３８】
登録命令は、登録レコードおよびレコードを登録した登録者情報を含む。データベース管理装置１０に入力された登録命令は、レコード登録部１１のプレフィックス生成手段２１およびインデックス登録手段２２に入力される（ステップ２２）。
【００３９】
プレフィックス生成手段２１は、入力された登録レコードの情報を用いて本登録操作に関わるBtreeインデックスを特定して、該当のBtreeインデックスに関するプレフィックス生成ルールを、プレフィックス生成ルール管理部１４から取得する（ステップ２３、２４）。プレフィックス生成ルール管理部１４では、各Btree毎に、登録レコードあるいはレコードの登録者情報を入力してプレフィックスを出力するプレフィックス生成ルールを保持している。
【００４０】
プレフィックス生成手段２１は、得られたプレフィックス生成ルールに登録レコード、レコードの登録者情報を適用することでプレフィックスを生成・出力する（ステップ２５）。
【００４１】
インデックス登録手段２２は、入力された登録レコードおよびプレフィックスから合成キーを導出して、この合成キーを用いてレコード管理部１３に格納されているインデックスおよびデータベースに登録レコードを登録する（ステップ２６）。
【００４２】
次に、図３を参照して、本実施の形態のデータベース管理装置１０におけるレコード検索操作の制御フローを説明する。図３に示すように、レコード検索部１２は、プレフィックス生成手段３１とインデックス検索手段３２を含む。なお、レコード検索部１２が、プレフィックス生成手段３１を備える代わりに、レコード検索部１２が、レコード登録部１１のプレフィックス生成手段２１を利用することとしてもよい。
【００４３】
クライアントプログラム２０を介して、データ操作者はレコード検索命令をデータベース管理装置１０に入力する（ステップ３１）。検索命令は、検索キー、検索対象の登録者情報を含む。
【００４４】
データベース管理装置１０に入力された検索命令は、レコード検索部１２のプレフィックス生成手段３１およびインデックス検索手段３２に入力される（ステップ３２）。プレフィックス生成手段３１は、入力された検索キーの情報を用いて本検索命令に関わる Btreeインデックスを特定して、該当のBtreeインデックスに関するプレフィックス生成ルールを、プレフィックス生成ルール管理部１４から取得する（ステップ３３、３４）。プレフィックス生成ルール管理部１４はまた、各Btree毎に、検索キーおよび検索対象の登録者情報を入力してプレフィックスを出力するプレフィックス生成ルールを保持している。
【００４５】
プレフィックス生成手段３１は、得られたプレフィックス生成ルールに検索キー、検索対象の登録者情報を適用することでプレフィックスを生成・出力する（ステップ３５）。
【００４６】
インデックス検索手段３２は、入力された検索キーおよびプレフィックスから合成キーを導出して、この合成キーを用いてレコード管理部１３に格納されているインデックスに対して検索命令を発行し（ステップ３６）、検索結果レコードを取得する（ステップ３７）。
【００４７】
結果として得られた検索結果レコードは、クライアントプログラム２０を介してデータ操作者に返却される（ステップ３８）。
【００４８】
なお、プレフィックス生成手段３１を備えずに、検索キーとして合成キーを入力し、この合成キーを用いてインデックス検索手段３２が検索を行うようにしてもよい。
【００４９】
次に、図４を参照して、プレフィックス生成手段２１、３１の処理フローを説明する。
【００５０】
レコード登録時に対応するプレフィックス生成手段２１は、ステップ４１において、入力された登録レコードの情報を用いて、本登録操作に関わるBtreeインデックスを特定する。そして、該当のBtreeインデックスに関するプレフィックス生成ルールを、プレフィックス生成ルール管理部１４から取得する。
【００５１】
ステップ４２では、プレフィックス生成手段２１は、登録レコードとレコードの登録者情報を用いて、ステップ４１で特定したプレフィックス生成ルールを適用して、プレフィックスを出力する。
【００５２】
レコード検索時に対応するプレフィックス生成手段３１は、ステップ４１において、検索キーの情報を用いて、本検索操作に関わるBtreeインデックスを特定する。そして、該当のBtreeインデックスに関するプレフィックス生成ルールを、プレフィックス生成ルール管理部から取得する。
【００５３】
ステップ４２では、プレフィックス生成手段３１は、検索キーと検索対象の登録者情報を用いて、ステップ４１で特定したプレフィックス生成ルールを適用して、プレフィックスを出力する。
【００５４】
（具体例）
以下、図面を参照して、具体例を説明する。
【００５５】
図５はツイート（登録商標）データ管理における第一の具体例を示す図である（以下の説明に記載された「ツイート」は登録商標である）。図５に示すように、本具体例におけるデータベーススキーマは、
(ツイートID，ツイート作成者ID，timezone，timestamp，ツイート内容，{ハッシュタグ}，…)
なるテーブル構造であり、ツイートIDが主キーである。また、Btreeインデックスは１つ構築されており、そのキーは (ツイート作成者ID，ツイートID)のマルチカラムインデックスになっている。
【００５６】
この例ではプレフィックスとして、ツイート作成者が属するtimezoneを用いる。この際のプレフィックス生成ルールは、
・レコード登録時にはレコードの登録者情報からtimezoneを抽出
・レコード検索時には検索対象の登録者情報からtimezoneを抽出
するというルールになる。
【００５７】
この結果、プレフィックスをインデックスのキーに付与して得られる合成キーは、
(timezone +ツイート作成者ID，ツイートID)
となる。ここで "+" はtimezoneの文字の値とツイート作成者IDの値を連結する操作である。こうして得られる合成キーを用いて、レコード登録時にはインデックスにレコードを登録する。
【００５８】
一方、レコードの検索時には合成キーを用いて、インデックスを利用してレコード検索を実行する。例えば、以下の二つの検索命令
検索命令1: 検索キー= (ツイート作成者ID)
検索命令2: 検索キー= (ツイート作成者ID，ツイートID)
は、合成キーを用いて
検索命令1: 合成キー = (timezone + ツイート作成者ID)
検索命令2: 合成キー =  (timezone + ツイート作成者ID，ツイートID)
と変換されて、インデックスを利用してレコード検索を実行する。
【００５９】
図６はツイートデータ管理における第二の具体例を示す図である。第二の具体例において、図５と異なる点はプレフィックスの箇所である。本例では、プレフィックスとして、あらかじめ利用者をクラスタ化して複数の利用者が属するコミュニティを抽出し、各コミュニティにIDを付与しておく。このコミュニティIDをレコードの登録者情報あるいは検索対象の登録者情報に加えておくことで、図５のtimezoneと同様にプレフィックスとしてコミュニティIDを利用する例になっている。
【００６０】
（実施の形態のまとめ、効果）
以上説明したように、プレフィックスを加えた合成キーを用いてBtreeインデックスにレコードを登録することによって、例えばツイートデータ管理では東京といった同一 timezoneに属する複数利用者から登録されたレコード群についてシーケンシャルなキーの挿入操作になる。この結果、複数のデータベース管理装置における負荷を分散すると同時に、インデックスに対するレコード登録操作がディスク装置においてシーケンシャルアクセスになり、その結果高速なレコード登録を実現することができる。
【００６１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６２】
１０  データベース管理装置
１１  レコード登録部
１２  レコード検索部
１３  レコード管理部
１４  プレフィックス生成ルール管理部
２１、３１  プレフィックス生成手段
２２  インデックス登録手段
３２  インデックス検索手段
【図１】
2013242674.tif 000003
【図２】
2013242674.tif 000004
【図３】
2013242674.tif 000005
【図４】
2013242674.tif 000006
【図５】
2013242674.tif 000007
【図６】
2013242674.tif 000008
【図７】
2013242674.tif 000009