JPS62182849A

JPS62182849A - デ−タ管理方式

Info

Publication number: JPS62182849A
Application number: JP61025125A
Authority: JP
Inventors: Kyoji Kawagoe; 恭二川越
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1986-02-06
Filing date: 1986-02-06
Publication date: 1987-08-11

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ファイルを有する計算機システムにおけるデ
ータ管理方式に関し、とくにデータの一部をキーとして
計算によってデータの格納番地を求めるハツシュによる
データアクセスを行なうときのデータ管理方式に関する
。

１′従来の技術〕従来、ファイルを用いたハツシュアクセス方式において
は、キー及びキー以外のデータは、他のデータと共にペ
ージと呼ばれるデータ格納域単位で蓄積される。このと
き、キー値から上記データ格納域と示す格納番地を求め
るにはハツシュ関数と呼ばれる特殊な計算式によってお
こなわれてきた。

しかして従来のデータ管理方式ではページの中の記憶域
が少なくなり、もはやこのページにはデータを格納する
ことができない、いわゆるオーバフローが発生したとき
にはオーバフローしたページにデータを格納できずにオ
ーバフローしたページを介して別の格納域に格納してい
た。

〔発明が解決しようとする問題点、１上記の従来のデータ管理方式ではデータの分布の偏りに
よりデータの格納効率が劣化し、またオーバフローした
データへのアクセスに際してはページアクセス回数が増
加するという問題点があった。

１、問題点を解決するための手段〕本発明の方式は、データの一部をキーとし、該キーのハ
ツシュ関数値により前記データのファイルへの格納域番
地を決定するデータアクセスを行なう情報処理装置のデ
ータ管理方式において、あらかじめデータ蓄積の際に記
憶された、オーバフローして格納されているデータを複
数のデータ格納域に分割したデータ格納域の番地列から
なる分割列データと前記ハツシュ関数値とがちデータの
格納域番地を決定する格納域番地決定手段と、データ蓄
積に際し前記格納域番地決定手段により決定された格納
域がオーバフローするときには該格納域の番地を前記分
割列データに追加して前記格納域番地決定手段により前
記オーバフローした格納域に格納されているデータおよ
び蓄積しようとしたデータの格納域番地を決定し蓄積す
るように制御する制御手段とを含んで構成される。

し作用〕前記の手段を有することにより、ページ数はオーバフロ
ーとともに増加することと、オーバフローしたページの
データのみ複数ページに分割することによりデータの均
質的な格納が可能となる。

また、オーバフローしたデータへのアクセスにおいても
、従来のようなオーバフロ一対応の格納域のアクセスが
不要であり、かつ分割列記憶域の参照にはファイルへの
アクセスが不要なことから、必ず１回のアクセスで所望
のデータを取り出すことが可能となる。

〔実施例〕

以下、本発明の実施例を図面を参照して説明する。

第１図は、本発明の一実施例を示すブロック図である。

データを蓄積する際には、まず外部からデータ値記憶部
１・１ヘデータが転送される。データ値内のキ一部のみ
ハツシュ計算部１２で使用され、適切な０から１に写像
する実数値が生成される。ハツシュ関数としては、任意
のものあるいはデータ分布状況からみて一様分布へ写像
する可能性の高い関数が選ばれる。例えば、関数として
Ｆ　（Ｘ）＝Ｘ／　（Ｘの取り得る最大値）が考えられ
る。得られたハツシュ関数値および以下で説明する分割
列記憶部１３内の分割列を用いて、第２図に示す動作に
より格納番地計算部１５で格納番地が計算される。デー
タアクセス制御部１４では以下に示ず処理が行なわれる
。格納番地計算部１５で得られた格納番地を有する格納
域をデータ取出部１６よりとりだし、もしオーバフロー
していなければデータ蓄積部１７にて上記格納域に上記
データを格納したのち、ディスク装置１８でディスクに
書き込む。もし、オーバフローしたページであればこの
ページのページ内データを各データのキーのハツシュ関
数値によって複数のページに分割する。

分割はまず分割列記憶部１３にオーバフローページの格
納域の番地を追加し、次いで各データを第２図のフロー
で処理し格納番地を求める。以降、単純な場合として２
分割のときを考えることとする。２分割されたデータ集
合は、上記オーバフロー巳なページと新にディスクの空
き領域から獲得されたページに格納される。与えられた
格納しようとするデータもそのハツシュ関数値によって
上記２つのページのいずれかに格納される。

データを収り出す際には、まず外部よりデータ値記憶部
１１ヘデータのキ一部のみ設定される。

上記キー値を用いてノ＼ツシュ計算部１２および格納番
地計算部１５にてＬ記蓄積の場合と同様にして格納域の
番地が決定されろ。その後、上記得られた番地よりデー
タ収出部１６より与えられたキー値を有するデータ格納
域が収り出され、データがデータ値記憶部１１へ設定さ
れる。

に記処理の詳細を例を用いてコ（２明する。

今、第３図に示すデータが第１１図のよつに格納されて
いるものとする。新に、データ（１５，ｆ＞を蓄積する
要求か与えられ、そのデータがデータ値記憶部１１に設
定されたものとする。分割列の内容は（１，，２）であ
る。まず、ハ・ソシュ計算部１２によりハツシュ関数値
が得られる。今、仮に０．２が計算でもとまったものと
する。このとき、つぎの格納番地計算部１５では、以下
に示す処理が行なわれる。

（ステップ１）初期値の設定　Ｎｒ）＝１．ｍ＝１、Ｐ
＝１．Ｎｅ＝１．１＝０（ステップ２＞１＝１（ステップ３）ｉ＞２でないからステ・ツブ４へ（ステ
ップ４）Ｌ、ｌ−１（ステ・ツブ５　）　Ｎ　ｌ！　＝　１．−　＋である
からステ・ンプ６．１へ（ステップ６．１）Ａ、＝Ｏであるからステップ７、Ｉ
ａ／＼（ステーツブ７．１ａ）Ｎｆｆ＝　１　、Ｎｐ＝２．ｍ
＝２（ステ・ｌア２　）　　ｉ　＝　２（スう゛・・Ｉプ３）ｉ＞　２でないからステ・・ｌプ
・１へ（、ス　テ　・・）　ア’−１）Ｌ２＝２（ステ
・ツブ５）Ｎｊ？＝Ｌｚでないからステ・ツブ６．２へ（ステップ６．２）　Ｎ　ｅ　＞　Ｌ　２でないがらス
テ・ソ７７．２ｂ’＼（７！、テ・ｙ７”７．２ｔ＋）Ｎｅ＝１．Ｎｐ＝３（
ステップ２＞　　ｉ　＝３（ステップ３）ｉ＞２であるから終了、Ｐ＝１これより
データの格納番地が１であることが得られた４ところが
、上記ページ１は既にオーバフロー状！ぶにありこれ以
上データを格納することができない。従って、ページ１
内のデータ集合を分割し、ページ１及び新しいページ４
に格納する。

このとき、蓄積すべき上記データもそのキーのハツシュ
関数値によって新しい分割列（１，２，１＞をもちい第
２図のフローチャーＩ・に従って適当なページ（１ある
いは４）に格納される。分割後のファイルの状態を第５
図に示す。

次に、第４図の状態でデータを取り出す際には、仮にデ
ータキー値が１２０でありそのハツシュ関数値が０．９
であるとしたとき、上の蓄積と同様にして以下のように
格納番地が設定される。

（ステップ１〉初期値の設定　Ｎｐ＝１．ｍ＝１、Ｐ＝
１．Ｎｅ＝１．１＝０（ステップ２）ｉ＝１（ステップ３）ｉ＞２でないからステップ４へ（ステッ
プ４）Ｌ＋＝１（ステップ５）Ｎｊ？＝Ｌ＋であるからステップ６．１
へ（ステップ６．１）　Ａ＋　＝　Ｏでないからステップ
７　、Ｉｈへ（ステップ７　、Ｉｂ）Ｐ　＝　２　、　Ｎ　ｅ　＝　
２　、　Ｎ　ｐ　＝　２、ｍ＝２（ステップ２）ｉ＝２（ステップ３）ｉ）・２でないからステップ４へ（ステ
ップ４）Ｌ２＝２（ステップ５）Ｎｅ＝Ｌ２であるからステップ６．１へ（ステップ６．１）　Ａ２　＝　０でないからステップ
７．１ｈへ（ステ・：ｔＴ）”７．１ｂ＞Ｐ＝３．Ｎｅ＝３．Ｎｐ
＝３、ｍ＝３（ステップ２）ｉ−＝３（ステップ３）ｉ＞２であるから終了。Ｐ＝３得られた
格納番地３からデータ取出部６によってキー１２０と一
致するデータ（１２０、ｄ）が取り出され、データ値記
憶部１１に設定され外部に渡される。

ｉ発明の効果〕このように、本発明にはオーバフローしたページに格納
されているデータの動的な分割および分割ページ番地を
有する分割列を用いた格納番地計算によって、ファイル
内のデータの分布を均質にでき、また必ず１回のアクセ
スでデータを収り出すことができ、アクセス回数を減少
できるという効果がある。実験および解析の結果、デー
タのページ格納効率は平均０．６７であり効率的なデー
タ格納が可能となった。

図面の節ｃｉｔな説明第１図は、本発明の一実施例を示すブロック図、第２図
は、第１図の格納番地計算部の動作フローチャー１・、
第３図は、第２図の説明にＣ重用するデータ集合の例を
示す図、第４図及び第５図は、第３図を用いた例におけ
る分割前後のファイル状態を示す説明図である。

１〜５．６．１．６．２．７．ｌａ　、　７．Ｉｂ　、
　７．２ａ　。

７．２ｂ・・・フローチャートのスデップ、１１・・・
データ飽記憶部、１２・・・ハツシュ計算部、１３・・
・分割列記憶部、１４・・・データアクセス制御部、１
５・・・格納番地計算部、１６・・・データ取出部、１
７・・・データ蓄積部、１８・・・ディスク装置。

躬　２ｆｆｉ熟３　凹番地　　　　　　　　　４地学４　図牛５図

Claims

【特許請求の範囲】データの一部をキーとし、該キーのハッシュ関数値によ
り前記データのフアイルへの格納域番地を決定するデー
タアクセスを行なう情報処理装置のデータ管理方式にお
いて、あらかじめデータ蓄積の際に記憶された、オーバフロー
して格納されているデータを複数のデータ格納域に分割
したデータ格納域の番地列からなる分割列データと前記
ハッシュ関数値とからデータの格納域番地を決定する格
納域番地決定手段と、データ蓄積に際し前記格納域番地
決定手段により決定された格納域がオーバフローすると
きには該格納域の番地を前記分割列データに追加して前
記格納域番地決定手段により前記オーバフローした格納
域に格納されているデータおよび蓄積しようとしたデー
タの格納域番地を決定し蓄積するように制御する制御手
段とを含むことを特徴とするデータ管理方式。