(57)【特許請求の範囲】
【請求項１】
主キーと副キーを含む値との組で構成されたレコードを前記値に含まれる副キーに基づいて検索するデータベースの検索方法であって、
同一の副キーを値に含む主キーに順序が割り当てられており、
前記データベースは、副キーと該副キーについて割り当てられた前記順序で最初の主キーである代表の主キーとを対応付けた副キー主キー対応テーブルと、主キーと副キーを含む値との組で構成され、該主キーが前記順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を前記値に含むレコードが蓄積される格納データテーブルとを記憶しており、
検索キーとして指定された副キーに対応付けられた前記代表の主キーを前記副キー主キー対応テーブルから検索し、
前記代表の主キーに一致する主キーを含むレコードを前記格納データテーブルから検索し、
検索されたレコードにＮＥＸＴ情報が含まれる場合は、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを前記格納データテーブルから検索する処理を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は終了することを特徴とするデータベースの検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースの副キーから主キーを検索するために使用されるメモリー領域を少なくする技術に関する。
【背景技術】
【０００２】
図９は、従来の分散KVSにおける格納データテーブルの例である。格納データテーブルには、例えば、電話加入者の情報が格納される。
【０００３】
従来の格納データテーブルは、多数のレコードを含み、各レコードは、主キーである電話番号、住所、氏名、副キーである契約ＩＤなどを含む。
【０００４】
この格納データテーブルを用いた主キー検索と称される検索方法では、電話番号（主キー）が入力され、格納データテーブルから、入力された電話番号（主キー）に一致する主キー（電話番号）を含むレコードが検索され、そのレコードから住所、氏名、契約ＩＤ（副キー）などが読み出される。
【０００５】
また、格納データテーブルを用いた副キー検索と称される検索方法では、契約ＩＤ（副キー）が入力され、格納データテーブルから、入力された契約ＩＤ（副キー）に一致する副キー（契約ＩＤ）を含むレコードが検索され、そのレコードから電話番号（主キー）などが読み出される。
【０００６】
格納データテーブルにおいては、複数のレコードが同じ副キー（契約ＩＤ）を含む場合がある。これらのレコードは、例えば、同一の企業に関するものであり、その企業の副キー（契約ＩＤ）を含む。
【０００７】
この場合、副キー検索では、その副キーと同じ契約ＩＤが入力されると、その複数のレコードが検索され、各レコードから電話番号（主キー）などが読み出される。つまり、複数の電話番号（主キー）が読み出される。
【０００８】
図１０は、従来の分散KVSにおける副キー主キー対応テーブルの例である。
従来の副キー主キー対応テーブルは、格納データテーブルを用いた副キー検索と同様に、副キー検索（副キーから主キーの検索）に使用される。
【０００９】
副キー主キー対応テーブルの各レコードは、入力される可能性のある１つの副キー（契約ＩＤ）と該副キーに対応する電話番号（主キー）の全てを予め含む。例えば、最大で１０の電話番号が検索される場合、各レコードは、１０の主キーの領域を含む。しかし、図に示すように、主キーが実際に格納される領域が少なく、無駄となる場合がある。
【００１０】
その課題の回避策として、図１１の例のように、副キー（契約ＩＤ）毎にテーブルを分けて管理する手法がある。
この手法での主キーテーブルは、格納データテーブルを用いた副キー検索と同様に、副キー検索（副キーから主キーの検索）に使用される。
【００１１】
主キーテーブルは、副キーごとの小テーブルを含み、小テーブルは、該当の副キーに対応する電話番号（主キー）の全てを予め含む。
【００１２】
例えば、契約ＩＤ「V0001-0002」に対応する小テーブルに１つの電話番号が含まれており、これに２つの電話番号を追加する場合、主キーテーブルは、まず、図１２のようになる。つまり、契約ＩＤ「V0001-0002」に対応する小テーブルがもう１つ生成（追加）される。この小テーブルには、既存の電話番号と追加の電話番号が含まれる。次に、電話番号が削除される場合の主キーテーブルは、図１３のようになる。つまり、既存の小テーブルから既存の電話番号が削除され、契約ＩＤ「V0001-0002」との対応づけもなくなる。よって、その領域は、その後、少なくともすぐには使用されず、無駄となる。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】「Range-Key Skip Graph による範囲検索可能な大規模分散キーバリューストアの実現」、情報処理学会研究報告、IPSJ SIG Notes 2010-DPS-144(9)、1-8、2010年9月10日
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は、上記課題に鑑みてなされたものであり、副キーから主キーを検索するために使用されるメモリー領域を少なくする技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記課題を解決するために、本発明のデータ構造は、主キーと副キーを含む値との組で構成されたレコードが蓄積される格納データテーブルから前記値に含まれる副キーに基づいてレコードを検索するためのデータ構造であって、同一の副キーを値に含む主キーに順序が割り当てられており、副キーと該副キーについて割り当てられた前記順序で最初の主キーである代表の主キーとを対応付けた副キー主キー対応テーブルと、主キーと副キーを含む値との組で構成され、該主キーが前記順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を前記値に含むレコードが蓄積される格納データテーブルと、を含み、検索キーとして指定された副キーに対応付けられた前記代表の主キーを前記副キー主キー対応テーブルから検索し、前記代表の主キーに一致する主キーを含むレコードを前記格納データテーブルから検索し、検索されたレコードにＮＥＸＴ情報が含まれる場合は、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを前記格納データテーブルから検索する処理を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は終了する処理に用いられることを特徴とする。
【００１６】
第１の本発明は、主キーと副キーを含む値との組で構成されたレコードを前記値に含まれる副キーに基づいて検索するデータベースの検索方法であって、同一の副キーを値に含む主キーに順序が割り当てられており、前記データベースは、副キーと該副キーについて割り当てられた前記順序で最初の主キーである代表の主キーとを対応付けた副キー主キー対応テーブルと、主キーと副キーを含む値との組で構成され、該主キーが前記順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を前記値に含むレコードが蓄積される格納データテーブルとを記憶しており、検索キーとして指定された副キーに対応付けられた前記代表の主キーを前記副キー主キー対応テーブルから検索し、前記代表の主キーに一致する主キーを含むレコードを前記格納データテーブルから検索し、検索されたレコードにＮＥＸＴ情報が含まれる場合は、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを前記格納データテーブルから検索する処理を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は終了することを特徴とする。
【発明の効果】
【００１７】
本発明によれば、副キーから主キーを検索するために使用されるメモリー領域を少なくできる。
【図面の簡単な説明】
【００１８】
【図１】本実施の形態に係るデータベースに含まれる副キー主キー対応テーブルの例である。
【図２】本実施の形態に係るデータベースに含まれる格納データテーブルの例である。
【図３】本データベースを含むシステム構成の例である。
【図４】本実施の形態に係る検索方法のフローチャートである。
【図５】検索のイメージを示す図である。
【図６】メモリ使用領域を従来技術と比較した図である。
【図７】本実施の形態におけるＣＰＵ使用率の遷移を示す図である。
【図８】本実施の形態における主キー検索時のメモリ使用領域と副キー検索時のメモリ使用領域を示す図である。
【図９】従来の分散データベースにおける格納データテーブルの例である。
【図１０】従来の分散データベースにおける副キー主キー対応テーブルの例である。
【図１１】従来の分散データベースにおける主キーテーブルの例である。
【図１２】図１１の主キーテーブルに１つの小テーブルが追加された場合の例である。
【図１３】図１２の主キーテーブルにおいて１つの小テーブルが空き領域となった場合の例である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について図面を参照して説明する。
【００２０】
図１は、本実施の形態に係るデータベースに含まれる副キー主キー対応テーブルの例である。図２は、本実施の形態に係るデータベースに含まれる格納データテーブルの例である。格納データテーブル２には、例えば、電話加入者の情報が格納される。
【００２１】
本実施の形態に係るデータベースは、副キーと該副キーに対応する１以上の主キーに割り当てられた順序で最初の主キーである代表の主キーとを含むレコードが蓄積される副キー主キー対応テーブル１と、主キーを少なくとも含み、該主キーが、同一の副キーに対応する２以上の主キーに割り当てられた順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を含むレコードが蓄積される格納データテーブル２とを備える。例えば、格納データテーブル２の各レコードは、加入者の住所、氏名などを含む。
【００２２】
ここでは、主キーを電話番号とし、副キーを契約ＩＤとするが、データベースの用途などによっては、別の情報を主キー、副キーとしてもよい。
【００２３】
例えば、契約ＩＤ（副キー）「V0001-0003」に電話番号（主キー）「050-2222-1111」、「050-3333-1234」、「050-4444-5678」が対応し、「050-2222-1111」に１、「050-3333-1234」に２、「050-4444-5678」に３の順序が割り当てられている場合、契約ＩＤ「V0001-0003」（副キー）およびこの順序で最初の主キーである代表の主キー「050-2222-1111」を含むレコードが副キー主キー対応テーブル１に含まれる。
【００２４】
また、格納データテーブル２は、電話番号「050-2222-1111」、「050-3333-1234」、「050-4444-5678」をそれぞれ含むレコードを含む。電話番号「050-2222-1111」を含むレコードは、「050-3333-1234」を示すＮＥＸＴ情報を含む。電話番号「050-3333-1234」を含むレコードは、「050-4444-5678」を示すＮＥＸＴ情報を含む。電話番号「050-4444-5678」は、最後の順序なので、電話番号「050-4444-5678」を含むレコードは、ＮＥＸＴ情報を含まない。
【００２５】
なお、契約ＩＤ（副キー）に電話番号（主キー）が１つだけ対応する場合は、この電話番号が代表の主キーとなる。
【００２６】
図３は、本データベースを含むシステム構成の例である。
データベースは、例えば、複数のノードＮ（コンピュータ）で構成される分散ＫＶＳデータベース１１において、各ノードＮに分散配置される。
【００２７】
分散ＫＶＳデータベース１１は、通信回線を介して接続されたデータ管理システム１２により管理される。データ管理システム１２は、例えば、オペレータに使用される保守装置１３に通信回線を介して接続される。データ管理システム１２は、例えば、複数のサービス提供装置１４に通信回線を介して接続される。各サービス提供装置１４は、複数の端末１５を収容する。
【００２８】
図４は、本実施の形態に係る検索方法のフローチャートである。
ここでは、データ管理システム１２による検索について説明するが、保守装置１３やサービス提供装置１４が同様の方法で検索してもよい。
【００２９】
（Ｓ１）
データ管理システム１２は、外部から契約ＩＤ（副キー）を入力する。
（Ｓ３）
次に、データ管理システム１２は、副キー主キー対応テーブル１から、Ｓ１で入力した契約ＩＤに一致する副キーを含むレコードを検索する。
【００３０】
（Ｓ５）
次に、データ管理システム１２は、Ｓ３で検索されたレコードから主キーを読み出す。
（Ｓ７）
次に、データ管理システム１２は、格納データテーブル２から、Ｓ５で検索された主キーに一致する主キーを含むレコードを検索する。
【００３１】
（Ｓ９）
次に、データ管理システム１２は、直前に検索された格納データテーブル２のレコードがＮＥＸＴ情報を含むか否かを判定する。
（Ｓ１１）
データ管理システム１２は、直前に検索された格納データテーブル２のレコードがＮＥＸＴ情報を含むなら（Ｓ９：ＹＥＳ）、格納データテーブル２から、当該ＮＥＸＴ情報により示される主キーを含むレコードを検索し、Ｓ９に戻る。
【００３２】
データ管理システム１２は、直前に検索された格納データテーブル２のレコードがＮＥＸＴ情報を含まないなら（Ｓ９：ＮＯ）、処理を終える。
【００３３】
図５は、検索のイメージを示す図である。
例えば、図１の例において、契約ＩＤ（副キー）「V0001-0003」を入力した場合、電話番号「050-2222-1111」、「050-3333-1234」、「050-4444-5678」（共に主キー）が検索される。電話番号「050-2222-1111」は代表の主キーである。電話番号「050-3333-1234」、「050-4444-5678」は、それぞれＮＥＸＴ情報により示される主キーである。
【００３４】
図６は、メモリ使用領域を従来技術と比較した図である。
格納データテーブル（２）においては、ＮＥＸＴ情報の追加により、従来よりもメモリ使用領域が増加する。
【００３５】
しかし、副キー主キー対応テーブル（１）においては、代表の主キーのみを保持したことにより、従来よりもメモリ使用領域が減少する。
【００３６】
トータルでは、代表の主キーのみを保持したことによるメモリ使用領域の減少量が、ＮＥＸＴ情報の追加によるメモリ使用領域の増加量より多いので、メモリ使用領域が減少する。
【００３７】
図７は、本実施の形態におけるＣＰＵ使用率の遷移を示す図である。
本実施の形態では、従来と同様に、電話番号（主キー）が入力されると、格納データテーブル２から、電話番号（主キー）に一致する主キー（電話番号）を含むレコードが検索され、そのレコードから住所、氏名、契約ＩＤ（副キー）などが読み出される。
【００３８】
本実施の形態では、このような主キー検索が行われることが殆どであり、図４のような副キー検索が行われるのは、全体の１０％程度である。副キー検索は、一時的にＣＰＵ使用率を高める。
【００３９】
図７に示すように、副キー検索が一時的にＣＰＵ使用率を高めたとしても、副キー検索の頻度は低いので、システムに与える悪影響は少ないと考えられる。
【００４０】
図８は、本実施の形態における主キー検索時のメモリ使用領域と副キー検索時のメモリ使用領域を示す図である。
主キー検索でのメモリ消費は少なく、空きのメモリを多く確保できる。一方、副キー検索でのメモリ消費は多く、空きのメモリを多く確保できない。
【００４１】
したがって、副キー検索時の空きのメモリを多く確保できるようにメモリ領域を多くしておくことが望ましい。
【００４２】
以上のように、本実施の形態のデータベースによれば、副キーと該副キーに対応する１以上の主キーに割り当てられた順序で最初の主キーである代表の主キーとを含むレコードが蓄積される副キー主キー対応テーブル１と、主キーを少なくとも含み、該主キーが、同一の副キーに対応する２以上の主キーに割り当てられた順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を含むレコードが蓄積される格納データテーブル２とを備える。そして、図４に示す副キー検索では、副キー主キー対応テーブル１の１つのレコードに含まれる代表の主キーに一致する主キーを含むレコードを格納データテーブル１から検索し（Ｓ７）、検索されたレコードにＮＥＸＴ情報が含まれる場合は（Ｓ９：ＹＥＳ）、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを格納データテーブル２から検索する処理（Ｓ１１）を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は（Ｓ９：ＮＯ）検索を終了するので、副キーから主キーを検索するために使用されるメモリー領域を少なくすることができる（図６）。
【００４３】
なお、図４に示す副キー検索をコンピュータに実行させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【００４４】
１  副キー主キー対応テーブル
２  格納データテーブル
１１  分散ＫＶＳデータベース
１２  データ管理システム
１３  保守装置
１４  サービス提供装置
１５  端末
Ｎ  ノード
【図１】
0006440256.tif 000002
【図２】
0006440256.tif 000003
【図３】
0006440256.tif 000004
【図４】
0006440256.tif 000005
【図５】
0006440256.tif 000006
【図６】
0006440256.tif 000007
【図７】
0006440256.tif 000008
【図８】
0006440256.tif 000009
【図９】
0006440256.tif 000010
【図１０】
0006440256.tif 000011
【図１１】
0006440256.tif 000012
【図１２】
0006440256.tif 000013
【図１３】
0006440256.tif 000014