JPH10124363A - 順編成索引管理方法 - Google Patents

Abstract

(57)【要約】 【課題】 格納されるエントリのキーの傾向が様々な場
合においても索引ブロック中の空き領域を低減させ、順
編成索引の記憶効率を向上させる。 【解決手段】 エントリを格納する際に当該エントリを
格納する対象の第１索引ブロックに空き領域がないと空
き領域検出手段３が検出した場合には、索引ブロック作
成手段４が新たな第２索引ブロックを作成し、エントリ
移動数算出手段５がエントリに関するキーの傾向に応じ
て指定されたエントリ移動ファクタに基づいて第１索引
ブロックから第２索引ブロックへ移動させるエントリ移
動数を決定し、当該エントリ移動数のエントリをエント
リ移動手段６が第１索引ブロックから第２索引ブロック
へ移動させる。したがって、第１索引ブロックと第２索
引ブロックとの空き領域を格納されるエントリに適した
配分にすることができ、後続するエントリを格納した場
合において、無駄な空き領域が発生することを防ぐこと
ができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、索引ブロックで構
成された順編成索引を管理する順編成索引管理方法に関
し、特に、エントリを格納するに足る空き領域のない索
引ブロックに対してエントリの格納が発生した場合に順
編成索引を拡張する順編成索引管理方法に関する。

【０００２】

【従来の技術】順編成索引としては、データベースシス
テムにおいては、例えば、B+-Treeという手法が利用さ
れている。B+-Treeとは「Douglas Comer. The Ubiquitou
s B-Tree. ACMComputing Surveys, 11(2):121-137,197
9」等で紹介されているように、動的なデータ構造であ
り、一般に二次記憶装置上において実現され、格納、削
除、ランダムサーチ、シーケンシャルサーチ等といった
データベースに対する処理をサポートしている。

【０００３】このようなB+-Treeの典型的な構成は、例
えば図７に示すように、上位の索引ブロック２１が下位
の索引ブロック２２を複数管理する構成となっており、
各下位の索引ブロック２２には、下位索引ブロックの次
の順序の索引ブロックを表すポインタを記憶する領域２
５と、キーとキーに対応する内容（バリュー）とを有し
たエントリを格納する領域２６とが、備えられている。

【０００４】このB+-Treeでは、索引ブロックにエント
リを格納する場合には、エントリを格納すべき第１索引
ブロックを検索し、当該第１索引ブロックにエントリを
格納するための空き領域が存在しない場合には、新たな
第２索引ブロックを作成し、第１索引ブロックに格納さ
れているエントリの５０％（変えることのできない固定
値）を第２索引ブロックに移動させることによって、順
編成索引全体を索引ブロック単位で拡張して動的なエン
トリの増加に対応している。

【０００５】しかしながら、上記したB+-Treeの方法で
は、順編成索引を拡張した時点では、第１索引ブロック
及び第２索引ブロックそれぞれに５０％の空き領域がで
きており、拡張した後に順編成索引に格納されるエント
リのキーの分布が一様でない場合、例えば、キーが大き
くなる傾向で複数のエントリが追加される場合、或いは
キーが小さくなる傾向で複数のエントリが追加される場
合には、前記索引ブロック中の５０％の空き領域がほと
んど未使用のままとなってしまい、順編成索引全体の記
憶効率が悪くなるという問題が生じていた。

【０００６】これに対して、特開平４−１０６６４１号
公報（以下、文献１という。）に記載された「索引の分
割率変更処理方式」では、上記した従来のB+-Treeの方
法において、エントリを追加する索引ブロックが階層の
最後の索引ブロックである場合に、当該索引ブロックに
空き領域が存在せず、且つ、格納するエントリのキーが
当該索引ブロックの最後のエントリのキーよりも大きい
時にのみ、元の索引ブロックから新たに作成した索引ブ
ロックにエントリを移動させず、格納対象のエントリの
みを新たな索引ブロックに格納するといった方法によっ
て、元の索引ブロック中に空き領域が発生することを防
ぎ、キーが昇順となっている複数のエントリが追加され
る状況での順編成索引の記憶効率を向上している。

【０００７】

【発明が解決しようとする課題】しかしながら、文献１
に記載された方法を用いた場合には、例えば、キーが昇
順となっていないが、全体としてキーが大きくなる傾向
で複数のエントリが追加される場合には、階層の最後の
索引ブロックのエントリの最大のキーより小さいキーを
持つエントリが格納されることもあるが、この時には、
従来のB+-Treeと同様な方法によって順編成索引の拡張
が行われるために、５０％の空き領域を持つ索引ブロッ
クを生じさせてしまい、後続のエントリを格納しても前
記空き領域をそのまま残してしまって順編成索引の記憶
効率を向上することができない。このように、文献１に
記載された方法では、キーの昇順となっているエントリ
が追加される場合を除いては、順編成索引の記憶効率を
向上することができない。

【０００８】本発明は、上記した従来の事情に鑑みなさ
れたもので、格納されるエントリのキーの傾向が様々な
場合においても索引ブロック中の空き領域を低減させ、
順編成索引の記憶効率を向上させる順編成索引管理方法
を提供することを目的としている。

【０００９】

【課題を解決するための手段】上記目的を達成するため
に本発明の請求項１に係る順編成索引管理方法は、索引
ブロックによって構成された順編成索引を管理する順編
成索引管理方法において、複数の索引ブロック間のエン
トリの移動数を規定するエントリ移動ファクタを、格納
されるエントリに関するキーの傾向に応じて順編成索引
に対して指定し、エントリを格納する際に第１索引ブロ
ックに当該エントリを格納するに足る空き領域がない場
合には、新たな第２索引ブロックを作成し、前記エント
リ移動ファクタに基づいて第１索引ブロックから第２索
引ブロックへ移動させるエントリ移動数を決定し、当該
エントリ移動数のエントリを第１索引ブロックから第２
索引ブロックへ移動させることを特徴とする。

【００１０】上記した請求項１に係る順編成索引管理方
法では、エントリ移動ファクタに基づいて第１索引ブロ
ックから第２索引ブロックへ移動するエントリ数が決定
されるために、順編成索引全体の索引ブロックに対する
エントリ移動ファクタを格納するエントリに関するキー
の傾向に応じて指定することによって、第１索引ブロッ
クと第２索引ブロックとの空き領域を格納されるエント
リに適した配分にすることができる。

【００１１】本発明の請求項２に係る順編成索引管理方
法は、索引ブロックによって構成された順編成索引を管
理する順編成索引管理方法において、複数の索引ブロッ
ク間のエントリの移動数を規定するエントリ移動ファク
タを、格納されるエントリに関するキーの傾向に応じて
索引ブロック毎に対して指定し、エントリを格納する際
に第１索引ブロックに当該エントリを格納するに足る空
き領域がない場合には、新たな第２索引ブロックを作成
し、前記エントリ移動ファクタに基づいて第１索引ブロ
ックから第２索引ブロックへ移動させるエントリ移動数
を決定し、当該エントリ移動数のエントリを第１索引ブ
ロックから第２索引ブロックへ移動させることを特徴と
する。

【００１２】上記した請求項２に係る順編成索引管理方
法では、エントリ移動ファクタに基づいて第１索引ブロ
ックから第２索引ブロックへ移動するエントリ数が決定
されるために、各索引ブロックに対するエントリ移動フ
ァクタを格納するエントリに関するキーの傾向に応じて
指定することによって、第１索引ブロックと第２索引ブ
ロックとの空き領域を格納されるエントリに適した配分
にすることができる。また、前記空き領域の配分を格納
する対象の索引ブロック毎に適した配分にすることがで
きる。

【００１３】本発明の請求項３に係る順編成索引管理方
法は、請求項１または請求項２に記載した順編成索引管
理方法において、前記エントリ移動ファクタを応用が指
定することを特徴とする。

【００１４】上記した請求項３に係る順編成索引管理方
法では、応用が把握している格納するエントリのキーの
傾向に応じて、第１索引ブロックと第２索引ブロックと
の空き領域を格納されるエントリに適した配分にするこ
とができる。

【００１５】本発明の請求項４に係る順編成索引管理方
法は、請求項１または請求項２に記載した順編成索引管
理方法において、エントリが格納される傾向に基づいて
前記エントリ移動ファクタを指定することを特徴とす
る。

【００１６】上記した請求項４に係る順編成索引管理方
法では、予め格納されるエントリのキーの傾向が分から
ない場合でも、順編成索引にエントリが格納される傾向
に基づいて、格納されるエントリのキーの傾向を推測で
き、第１索引ブロックと第２索引ブロックとの空き領域
を格納されるエントリに適した配分にすることができ
る。

【００１７】本発明の請求項５に係る順編成索引管理方
法は、請求項１または請求項２に記載した順編成索引管
理方法において、前記エントリ移動ファクタとして複数
のエントリ移動ファクタが指定され、前記複数のエント
リ移動ファクタ中に応用によって指定されているエント
リ移動ファクタがある場合には、当該応用によって指定
されたエントリ移動ファクタに基づいてエントリ移動数
を決定することを特徴とする。

【００１８】上記した請求項５に係る順編成索引管理方
法では、応用がエントリ移動ファクタを指定している場
合には、他のエントリ移動ファクタが指定されていて
も、応用が指定したエントリ移動ファクタによって、第
１索引ブロックと第２索引ブロックとの空き領域の配分
を決定する。

【００１９】

【発明の実施の形態】本発明に係る順編成索引管理方法
を実施する順編成索引管理装置の一実施例を図１を参照
して説明する。この順編成索引管理装置は、順編成索引
に格納するエントリを入力するエントリ入力手段１と、
格納するエントリを格納すべき第１索引ブロックを特定
する索引ブロック特定手段２と、特定された第１索引ブ
ロックに空き領域があるか否かを検出する空き領域検出
手段３と、空き領域がないことを検出されたことに基づ
いて新たな第２索引ブロックを作成する索引ブロック作
成手段４と、第１索引ブロックから第２索引ブロックへ
移動するエントリ移動数を算出するエントリ移動数算出
手段５と、算出されたエントリ移動数のエントリを第１
索引ブロックから第２索引ブロックへ移動するエントリ
移動手段６と、入力されたエントリを索引ブロックに格
納する入力エントリ格納手段７と、エントリが格納され
る傾向からエントリ移動ファクタを算出する移動ファク
タ算出手段８と、エントリ移動ファクタを管理する移動
ファクタ管理手段９と、を備えている。

【００２０】まず、上記した順編成索引管理装置が管理
する順編成索引を図２を参照して説明する。なお、図７
に示す従来の順編成索引と同一部分には同一番号を付
し、重複する説明を省略する。この順編成索引は、図７
に示す従来の順編成索引に、さらに索引ブロック２２内
に格納しているエントリの数を保持するエントリ数保持
領域２３と、当該索引ブロックに対するエントリ移動フ
ァクタを保持する移動ファクタ保持領域２４と、を備え
ている。

【００２１】次に、上記した順編成索引管理装置を詳細
に説明する。空き領域管理手段３は、索引ブロック特定
手段２によって特定された第１索引ブロック中のエント
リ保持領域２３のエントリ数に基づいて、第１索引ブロ
ックに空き領域があるか否かを検出し、空き領域がない
と検出した場合には索引ブロック作成手段４に空き領域
がないことを通知する。一方、空き領域があると検出し
た場合には、入力エントリ格納手段７に入力されたエン
トリを格納させる指示を行う。索引ブロック作成手段４
は、空き領域管理手段３から空き領域がないとの通知を
受け取ると、第１索引ブロックの直後に繋がる新たな第
２索引ブロックを作成する。

【００２２】エントリ移動数算出手段５は、索引ブロッ
ク作成手段４によって第２索引ブロックが作成された場
合に動作し、移動ファクタ管理手段９からエントリ移動
ファクタを受け取る。次いで、第１索引ブロックから第
２索引ブロックへ移動させるエントリの移動数を以下の
式（１）を用いて算出し、算出したエントリ移動数をエ
ントリ移動手段６に通知する。

【００２３】

【数１】

【００２４】エントリ移動手段６は、通知されたエント
リ移動数のエントリを第１索引ブロックからキーの大き
い順に取り出し、第２索引ブロックへ移動させて格納
し、エントリ入力手段１によって入力されたエントリを
格納させる指示を入力エントリ格納手段７に行う。ここ
で、索引ブロック間で移動するエントリの数を規定する
エントリ移動ファクタは、”０”〜”１”の間の数値と
なっており、エントリ移動数算出手段５及びエントリ移
動手段６の処理によってエントリ移動ファクタが”０”
に近いほど第２索引ブロックに移動するエントリ移動数
が多く、第１索引ブロックの空き領域が多くなる。一
方、”１”に近いほど第２索引ブロックに移動するエン
トリ移動数が少なく、第２索引ブロックの空き領域が多
くなる。

【００２５】したがって、格納されるエントリのキーが
増加傾向であれば、エントリ移動ファクタを”１”に近
い値とし、逆に、エントリのキーが減少傾向であればエ
ントリ移動ファクタを”０”に近い値としておくことに
よって、第１索引ブロックと第２索引ブロックとの空き
領域の配分をエントリのキーの傾向に適したものとする
ことができ、後続するエントリが格納されていく際に、
無駄な空き領域が発生することを防ぐことができる。

【００２６】入力エントリ格納手段７は、エントリ移動
手段６から入力エントリの格納指示を受け取った場合に
は、第１索引ブロック或いは第２索引ブロックのいずれ
に格納するかを入力エントリのキーに基づいて決定し、
決定した索引ブロック中のキーに応じた位置に入力エン
トリを格納する。なお、空き領域検出手段３から入力エ
ントリの格納指示を受け取った場合には、第１索引ブロ
ックの入力エントリーのキーに応じた位置にエントリを
格納する。

【００２７】移動ファクタ算出部８は、索引ブロック毎
にエントリが格納される傾向に基づいてエントリ移動フ
ァクタを算出する。すなわち、エントリが空の状態から
格納されていく場合の索引ブロックのエントリ移動ファ
クタは、例えば以下に示すように算出される。空の索引
ブロックのエントリ移動ファクターを初期値”０”と
し、空の索引ブロックに対して最初にエントリを格納す
る場合のエントリ移動ファクタの増加を”０”とする。
また、ｎ個（０＜ｎ≦Ｓ）のエントリが格納されている
索引ブロックに対してエントリを格納する場合のエント
リ移動ファクタの増加Ｍｎは以下の式（２）によって求
める。

【００２８】

【数２】

【００２９】したがって、空の状態からエントリが格納
された索引ブロックを拡張する際のエントリ移動ファク
タＭｅは以下の式（３）で算出される。

【００３０】

【数３】

【００３１】例えば、図４に示す上から１０個のエント
リが空の索引ブロックに格納された場合には、以下の式
（４）に示すようにエントリ移動ファクタが算出され
る。

【００３２】

【数４】

【００３３】なお、エントリ移動ファクタが０．７５２
となっている空き領域のない索引ブロックに対してエン
トリが格納される場合には、新たに作成される索引ブロ
ックには、以下の式（５）に示すように２個のエントリ
が移動されることとなる。

【００３４】

【数５】

【００３５】また、新たに作成された際にｊ個のエント
リが移動された索引ブロックに対してのエントリ移動フ
ァクタは、例えば、以下のように算出される。まず、空
の索引ブロックのエントリ移動ファクターを初期値”
０”とし、移動されたエントリの中の１つのエントリに
よるエントリ移動ファクタの増加を”０”とする。ま
た、移動されたエントリ中の他のエントリについては、
各エントリによるエントリ移動ファクターの増加を０．
５／（Ｓ−１）とする。よって、ｊ個のエントリが移動
された索引ブロックがエントリを格納して、空き領域が
なくなった時点でのエントリ移動ファクターＭｅは以下
の式（６）で求められる。

【００３６】

【数６】

【００３７】上記した式（３）及び式（４）によって算
出されるエントリ移動ファクタは、エントリがキーの減
少する傾向で格納されている場合には、”０”に近い値
となり、特にエントリのキーが降順で格納されている場
合には”０”となる。また、エントリがキーの増加する
傾向で格納されている場合には”１”に近い値となり、
特に、エントリが昇順で格納されている場合には”１”
となる。したがって、格納されるエントリのキーの傾向
を予め知らない場合であっても、格納されるエントリの
キーの傾向を把握することができ、上記したエントリ移
動数算出手段４及びエントリ移動手段５による処理によ
って、第１索引ブロック及び第２索引ブロックの空き領
域の配分を、格納されるエントリのキーの傾向に適した
ものとすることができる。

【００３８】移動ファクタ管理部９は、移動ファクタ算
出手段８によって算出されたエントリ移動ファクタを索
引ブロック中の移動ファクタ保持領域２４に格納する。
また、応用からエントリ移動ファクタの指定があった場
合には、指定されたエントリ移動ファクタをメモリ（図
示せず）に保持する。そして、移動ファクタ管理部９
は、エントリ移動数算出手段５からエントリ移動ファク
タの要求があった場合には、応用によって指定されたエ
ントリ移動ファクタがあれば、当該エントリ移動ファク
タをエントリ移動数算出手段５に渡す一方、応用によっ
て指定されていなければ、第１索引ブロックの移動ファ
クタ保持領域２４に保持されたエントリ移動ファクタを
エントリ移動数算出手段５に渡す。

【００３９】上記したように、応用からエントリ移動フ
ァクタの指示を優先的に使用することによって、格納さ
れるエントリについて応用が把握している正確なキーの
傾向（例えば、昇順、降順）に基づいて第１索引ブロッ
クと第２索引ブロックとの空き領域を適切に配分するこ
とができる。

【００４０】ここで、応用は、エントリがキーの増加傾
向で格納される場合には、エントリ移動ファクタを”
１”に近い値を指定し、特に昇順で格納される場合に
は”１”を指定しており、一方、エントリが減少傾向で
格納される場合には、”０”に近い値を指定し、特に降
順で格納される場合には”０”を指定している。なお、
応用を、格納するエントリのキーの傾向が変化する毎に
エントリ移動ファクタを動的に指定させるようにしても
よい。

【００４１】なお、上記した各機能手段はＣＰＵがプロ
グラムに従って処理を実行することにより構成される
が、これら機能手段を独立したハードウエア回路として
構成することもできる。

【００４２】次に、上記した順編成索引管理装置による
順編成索引管理方法を図３を参照して説明する。応用か
らエントリ入力手段１がエントリを取得すると当該エン
トリを索引ブロック特定手段２に渡す（ステップＳ
１）。索引ブロック特定手段２は、エントリを受け取る
と、当該エントリ中のキーから格納する対象の第１索引
ブロックを特定し、当該第１索引ブロックを空き領域検
出手段２に通知する（ステップＳ２）。

【００４３】通知された空き領域検出手段２は、当該第
１索引ブロックに空き領域があるか否かを検出し（ステ
ップＳ３）、空き領域がないと検出した場合には、空き
領域がないことを索引ブロック作成手段４に通知し、通
知された索引ブロック作成手段４は、新たな第２索引ブ
ロックを作成する（ステップＳ４）。

【００４４】新たな第２索引ブロックが作成されると、
エントリ移動数算出手段５が移動ファクタ管理手段９に
エントリ移動ファクタを要求する。要求を受けた移動フ
ァクタ管理手段９は応用から指定されたエントリ移動フ
ァクタがある場合には、当該エントリ移動ファクタをエ
ントリ移動数算出手段に返送する一方、応用から指定が
ない場合には、第１索引ブロックの移動ファクタ保持領
域２４に保持されたエントリ移動ファクタをエントリ移
動数算出手段５に返送する（ステップＳ５、Ｓ６、Ｓ
７）。

【００４５】エントリ移動ファクタが返送されると、当
該エントリ移動ファクタに基づいてエントリ移動数算出
手段５はエントリ移動数を算出し、結果をエントリ移動
手段６に通知する（ステップＳ８）。エントリ移動数を
通知されたエントリ移動手段６は、エントリ移動数に対
応するエントリを第１索引ブロックから第２索引ブロッ
クへ移動させ（ステップＳ９）、さらに、第１索引ブロ
ック及び第２索引ブロックのエントリ数を再設定する。
また、このときに移動ファクタ算出手段８は、エントリ
移動ファクタを算出して索引ブロックに再設定する（ス
テップＳ１０）。

【００４６】次いで、入力エントリ格納手段７が応用か
ら入力されたエントリのキーに基づいて、格納する索引
ブロックを特定するとともに索引ブロック内の位置を特
定し、該当する位置にエントリを格納し（ステップＳ１
１）、格納した索引ブロックのエントリ数を再設定す
る。また、このときに移動ファクタ算出手段８は、エン
トリ移動ファクタを算出して索引ブロックに再設定する
（ステップＳ１２）。

【００４７】なお、空き領域検出手段３によって入力さ
れたエントリを格納する対象の索引ブロックに空き領域
あると検出された場合には、入力エントリ格納手段７が
当該索引ブロック中の入力エントリのキーに応じた位置
に入力エントリを格納し（Ｓ１１）、索引ブロック内の
エントリ数を再設定する。また、このときに移動ファク
タ算出手段８は、エントリ移動ファクタを算出して索引
ブロックに再設定する（ステップＳ１２）。

【００４８】次に、上記した本発明に係る順編成索引管
理方法によって、図４に示すキーとバリューとの組から
なるエントリ群を順次格納した場合の順編成索引の記憶
効率を説明する。なお、順編成索引は予め空の索引ブロ
ックを一つ持っているものとし、索引ブロックには１０
個のエントリを格納することができるものとする。ま
た、応用は１３番目以降のエントリがキーの昇順となっ
ていることを予め把握しているものとする。

【００４９】１６番目までのエントリを格納した後の順
編成索引は図５に示す状態となり、この場合は２０個の
エントリ格納可能領域に対して１６個のエントリが格納
されており、順編成索引の記憶効率は１６／２０＝０．
８となる。さらに２６番目までのエントリを格納する場
合には、キーの昇順でエントリが格納されることを応用
が予め把握しているので、応用の指示によって順編成索
引に対してエントリ移動ファクタを”１”に設定するこ
とができ、新たな索引ブロックを作成する際には、当該
新たな索引ブロックにはエントリを移動させず、キーが
昇順となっているエントリを効率よく格納することがで
きる。この結果、２６番目までのエントリを格納した後
の順編成索引は図６に示す状態となり、順編成索引の記
憶効率は２６／３０＝０．８７となる。

【００５０】なお、上記したように応用からエントリ移
動ファクタの指示がない場合でも、エントリの格納され
る傾向に基づいてエントリを格納しきれない索引ブロッ
クに対して算出されるエントリ移動ファクタは０．９４
となるので、新たな索引ブロックへ移動するエントリの
数は１個だけであり、多くの無駄な空き領域が発生する
ことが防げ、２６番目までエントリを格納した後の順編
成索引の記憶効率は２６／３０＝０．８７となってい
る。

【００５１】これに対して、上記同様なエントリ群を文
献１に記載された方法で格納すると、新たな索引ブロッ
クを作成するときには、エントリのキーが索引ブロック
中で最大でなければ、エントリを格納しきれない索引ブ
ロック及び新たに作成された索引ブロックのいずれの索
引ブロックにも、常に５０％の空き領域ができてしま
う。したがって、１６番目までのエントリを格納した後
は図８に示す状態となってしまい、順編成索引の記憶効
率は１６／３０＝０．５３となって、記憶効率が悪い。
また、２６番目までのエントリを格納した後でも、順編
成索引の記憶効率は２６／４０＝０．６５となってお
り、記憶効率が悪い。

【００５２】上記したように、順編成索引を拡張する際
に、キーの傾向に応じてエントリの移動を行うことがで
き、第１索引ブロック及び第２索引ブロックの空き領域
を格納されるエントリに適した配分に変えることができ
る。したがって、後続するエントリが格納された場合に
は、無駄な空き領域が残ってしまうといった状況を防
げ、順編成索引の記憶効率を向上することができる。

【００５３】なお、エントリ移動ファクタは上記に限ら
ず、エントリの移動数そのものでもよく、要は、第１索
引ブロックから第２索引ブロックへ移動させるエントリ
の数を規定するものであればよい。また、上記した実施
例では、順編成索引のブロック２２内にエントリ数保持
領域２３を備えて、当該索引ブロック中のエントリ数を
把握していたが、エントリ数保持領域２３を索引ブロッ
ク２２内に備えずに、例えば、索引ブロックに格納され
ているデータ量に基づいてエントリ数を算出して把握す
るようにしてもよい。また、上記した実施例では応用が
順編成索引に対してエントリ移動ファクタを指定してい
たが、各索引ブロック毎にエントリ移動ファクタを指定
するようにしてもよい。

【００５４】また、上記した実施例では、エントリが格
納される傾向に基づいて各索引ブロック毎にエントリ移
動ファクタを指定して、各索引ブロック毎に適した空き
領域を配分させるようにしていたが、順編成索引全体に
対してエントリ移動ファクタを指定するようにしてもよ
い。また、上記した実施例では、エントリが格納される
傾向に基づいてエントリ移動ファクタを指定するととも
に、応用がエントリ移動ファクタを指定できるようにし
ていたが、いずれか一方のエントリ移動ファクタだけを
指定するようにしてもよい。

【００５５】なお、上記した実施例では、エントリを索
引ブロックに格納する際に、実際に索引ブロック中に空
き領域があるか否かを検出し、空き領域がないと検出し
た場合に順編成索引の拡張処理を行っていたが、格納す
るエントリを格納するに足る空き領域が索引ブロックに
あるか否かを予め検出し、空き領域が足りないと検出し
た場合に順編成索引の拡張処理を行うようにしてもよ
い。なお、上記した実施例では、B+-Treeによる順編成
索引を例にとって説明したが、B+-Treeによる順編成索
引に限らず、複数のエントリを格納する索引ブロックで
構成された順編成索引であれば本発明を適用することが
できる。

【００５６】

【発明の効果】以上説明したように、本発明の順編成索
引管理方法によると、エントリ移動ファクタを格納する
エントリに関するキーの傾向に応じて指定し、当該エン
トリ移動ファクタに基づいて第１索引ブロックから第２
索引ブロックへ移動するエントリ数を決定するようにし
たために、第１索引ブロックと第２索引ブロックとの空
き領域を格納されるエントリに適した配分にすることが
できる。したがって、格納されるエントリのキーの傾向
が様々な場合であっても、空き領域の発生を防ぎ、効率
よく順編成索引へ格納することができる。さらに、順編
成索引の記憶効率がよいために、当該順編成索引を使用
した検索、格納等といった処理の効率を向上することが
できる。

【図面の簡単な説明】

【図１】 本発明に係る順編成索引管理方法を実施する
順編成索引管理装置の構成図である。

【図２】 本発明に係る順編成索引管理方法で管理する
順編成索引の構成図である。

【図３】 本発明に係る順編成索引管理方法を説明する
フローチャートである。

【図４】 エントリを格納される順番で並べた図であ
る。

【図５】 本発明に係る順編成索引管理方法によって１
６番目までのエントリを格納した時の順編成索引の状態
を示す図である。

【図６】 本発明に係る順編成索引管理方法によって２
６番目までのエントリを格納した時の順編成索引の状態
を示す図である。

【図７】 従来例における順編成索引の構成図である。

【図８】 従来の方法により１６番目までのエントリを
格納した時の順編成索引の状態を示す図である。

【符号の説明】

１・・エントリ入力手段、 ２・・索引ブロック特定
手段、３・・空き領域検出手段、 ４・・索引ブロッ
ク作成手段、５・・エントリ移動数算出手段、６・・エ
ントリ移動手段、７・・入力エントリ格納手段、 ８・
・移動ファクタ算出手段、９・・移動ファクタ管理手
段、２２・・エントリ数保持領域、 ２４・・移動ファ
クタ保持領域、

Claims (5)

【特許請求の範囲】
1. 【請求項１】索引ブロックによって構成された順編成索
   引を管理する順編成索引管理方法において、 複数の索引ブロック間のエントリの移動数を規定するエ
   ントリ移動ファクタを、格納されるエントリに関するキ
   ーの傾向に応じて順編成索引に対して指定し、 エントリを格納する際に第１索引ブロックに当該エント
   リを格納するに足る空き領域がない場合には、新たな第
   ２索引ブロックを作成し、前記エントリ移動ファクタに
   基づいて第１索引ブロックから第２索引ブロックへ移動
   させるエントリ移動数を決定し、当該エントリ移動数の
   エントリを第１索引ブロックから第２索引ブロックへ移
   動させることを特徴とする順編成索引管理方法。
2. 【請求項２】索引ブロックによって構成された順編成索
   引を管理する順編成索引管理方法において、 複数の索引ブロック間のエントリの移動数を規定するエ
   ントリ移動ファクタを、格納されるエントリに関するキ
   ーの傾向に応じて索引ブロック毎に対して指定し、 エントリを格納する際に第１索引ブロックに当該エント
   リを格納するに足る空き領域がない場合には、新たな第
   ２索引ブロックを作成し、前記エントリ移動ファクタに
   基づいて第１索引ブロックから第２索引ブロックへ移動
   させるエントリ移動数を決定し、当該エントリ移動数の
   エントリを第１索引ブロックから第２索引ブロックへ移
   動させることを特徴とする順編成索引管理方法。
3. 【請求項３】請求項１または請求項２に記載した順編成
   索引管理方法において、前記エントリ移動ファクタを応
   用が指定することを特徴とする順編成索引管理方法。
4. 【請求項４】請求項１または請求項２に記載した順編成
   索引管理方法において、エントリが格納される傾向に基
   づいて前記エントリ移動ファクタを指定することを特徴
   とする順編成索引管理方法。
5. 【請求項５】請求項１または請求項２に記載した順編成
   索引管理方法において、前記エントリ移動ファクタとし
   て複数のエントリ移動ファクタが指定され、前記複数の
   エントリ移動ファクタ中に応用によって指定されている
   エントリ移動ファクタがある場合には、当該応用によっ
   て指定されたエントリ移動ファクタに基づいてエントリ
   移動数を決定することを特徴とする順編成索引管理方
   法。