JP6440256B2

JP6440256B2 - データベースの検索方法

Info

Publication number: JP6440256B2
Application number: JP2015027395A
Authority: JP
Inventors: 信一河村; 秋山　悟; 悟秋山
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2015-02-16
Filing date: 2015-02-16
Publication date: 2018-12-19
Anticipated expiration: 2035-02-16
Also published as: JP2016151793A

Description

本発明は、データベースの副キーから主キーを検索するために使用されるメモリー領域を少なくする技術に関する。

図９は、従来の分散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」は、それぞれＮＥＸＴ情報により示される主キーである。

図６は、メモリ使用領域を従来技術と比較した図である。
格納データテーブル（２）においては、ＮＥＸＴ情報の追加により、従来よりもメモリ使用領域が増加する。

しかし、副キー主キー対応テーブル（１）においては、代表の主キーのみを保持したことにより、従来よりもメモリ使用領域が減少する。

トータルでは、代表の主キーのみを保持したことによるメモリ使用領域の減少量が、ＮＥＸＴ情報の追加によるメモリ使用領域の増加量より多いので、メモリ使用領域が減少する。

図７は、本実施の形態におけるＣＰＵ使用率の遷移を示す図である。
本実施の形態では、従来と同様に、電話番号（主キー）が入力されると、格納データテーブル２から、電話番号（主キー）に一致する主キー（電話番号）を含むレコードが検索され、そのレコードから住所、氏名、契約ＩＤ（副キー）などが読み出される。

本実施の形態では、このような主キー検索が行われることが殆どであり、図４のような副キー検索が行われるのは、全体の１０％程度である。副キー検索は、一時的にＣＰＵ使用率を高める。

図７に示すように、副キー検索が一時的にＣＰＵ使用率を高めたとしても、副キー検索の頻度は低いので、システムに与える悪影響は少ないと考えられる。

図８は、本実施の形態における主キー検索時のメモリ使用領域と副キー検索時のメモリ使用領域を示す図である。
主キー検索でのメモリ消費は少なく、空きのメモリを多く確保できる。一方、副キー検索でのメモリ消費は多く、空きのメモリを多く確保できない。

したがって、副キー検索時の空きのメモリを多く確保できるようにメモリ領域を多くしておくことが望ましい。

以上のように、本実施の形態のデータベースによれば、副キーと該副キーに対応する１以上の主キーに割り当てられた順序で最初の主キーである代表の主キーとを含むレコードが蓄積される副キー主キー対応テーブル１と、主キーを少なくとも含み、該主キーが、同一の副キーに対応する２以上の主キーに割り当てられた順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を含むレコードが蓄積される格納データテーブル２とを備える。そして、図４に示す副キー検索では、副キー主キー対応テーブル１の１つのレコードに含まれる代表の主キーに一致する主キーを含むレコードを格納データテーブル１から検索し（Ｓ７）、検索されたレコードにＮＥＸＴ情報が含まれる場合は（Ｓ９：ＹＥＳ）、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを格納データテーブル２から検索する処理（Ｓ１１）を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は（Ｓ９：ＮＯ）検索を終了するので、副キーから主キーを検索するために使用されるメモリー領域を少なくすることができる（図６）。

なお、図４に示す副キー検索をコンピュータに実行させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。

１副キー主キー対応テーブル
２格納データテーブル
１１分散ＫＶＳデータベース
１２データ管理システム
１３保守装置
１４サービス提供装置
１５端末
Ｎノード

Claims

主キーと副キーを含む値との組で構成されたレコードを前記値に含まれる副キーに基づいて検索するデータベースの検索方法であって、
同一の副キーを値に含む主キーに順序が割り当てられており、
前記データベースは、副キーと該副キーについて割り当てられた前記順序で最初の主キーである代表の主キーとを対応付けた副キー主キー対応テーブルと、主キーと副キーを含む値との組で構成され、該主キーが前記順序で最後以外の主キーである場合は、該主キーの次の順序を割り当てられた主キーを示すＮＥＸＴ情報を前記値に含むレコードが蓄積される格納データテーブルとを記憶しており、
検索キーとして指定された副キーに対応付けられた前記代表の主キーを前記副キー主キー対応テーブルから検索し、
前記代表の主キーに一致する主キーを含むレコードを前記格納データテーブルから検索し、
検索されたレコードにＮＥＸＴ情報が含まれる場合は、当該ＮＥＸＴ情報により示される主キーに一致する主キーを含むレコードを前記格納データテーブルから検索する処理を、レコードにＮＥＸＴ情報が含まれる場合は繰り返し、レコードにＮＥＸＴ情報が含まれない場合は終了することを特徴とするデータベースの検索方法。