JPS60181849A - インデツクス管理方式 - Google Patents
インデツクス管理方式Info
- Publication number
- JPS60181849A JPS60181849A JP59037074A JP3707484A JPS60181849A JP S60181849 A JPS60181849 A JP S60181849A JP 59037074 A JP59037074 A JP 59037074A JP 3707484 A JP3707484 A JP 3707484A JP S60181849 A JPS60181849 A JP S60181849A
- Authority
- JP
- Japan
- Prior art keywords
- index
- record
- type
- key value
- occurrence
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は、データベース管理システムにおいて、ファイ
ル装置上の内容検索処理を高速に実現するだめのインデ
ックス管理方式に関する。
ル装置上の内容検索処理を高速に実現するだめのインデ
ックス管理方式に関する。
（従来技術）
従来からインデックスにはＢ＋ トリーと呼ばれている
方式を採用することが多い。Ｂ トリーでは常に１個の
最高位ノード（ルートと呼ぶ）が存在するように保証し
、各ノードは下位ノードに含ま力ている最大キー値と、
そのノードへのポインタから構成されている一対のレコ
ードオカレンス、すなわち、インデックスレコードオカ
レンスト’に複数個を含み、インデックスレコードオカ
レンスはキー値順にノードされている。あるノードに舎
外れているすべてのインデックスレコードオカレンスを
示すポインタが、そのキー値を保持しているレコードオ
カレンスを示す時には、このノード’ｆ： Ｒ５′下位
ノードと呼び、最下位ノードが持っているインデックス
レコードオカレンスの個数と、アクセス対象レコードオ
カレンスの個数とは一致している。
方式を採用することが多い。Ｂ トリーでは常に１個の
最高位ノード（ルートと呼ぶ）が存在するように保証し
、各ノードは下位ノードに含ま力ている最大キー値と、
そのノードへのポインタから構成されている一対のレコ
ードオカレンス、すなわち、インデックスレコードオカ
レンスト’に複数個を含み、インデックスレコードオカ
レンスはキー値順にノードされている。あるノードに舎
外れているすべてのインデックスレコードオカレンスを
示すポインタが、そのキー値を保持しているレコードオ
カレンスを示す時には、このノード’ｆ： Ｒ５′下位
ノードと呼び、最下位ノードが持っているインデックス
レコードオカレンスの個数と、アクセス対象レコードオ
カレンスの個数とは一致している。
Ｂ″゛゛トリー構造つインデックスは、新規のキー値を
持ったレコードオカレンスを追加する場合においても、
あるいは重複キー値を有するレコードオカレンスを追加
する場合においても最下位ノードの該当する箇所へその
キー値を含むインデックスレコードオカレンスｅ作成Ｌ
、既４ ＝ｙテｙクスレコードオカレンスと論理順序と
を保証している。したがって、Ｂ＋トリー構造をもつ従
来のインデックスでの母集団のレコード群の件数に比例
してインデックスを構成しているノードが増加し、重複
キー値をもつ件数が増加してもインデックスオカレンス
の個数が減らないという欠点があった。
持ったレコードオカレンスを追加する場合においても、
あるいは重複キー値を有するレコードオカレンスを追加
する場合においても最下位ノードの該当する箇所へその
キー値を含むインデックスレコードオカレンスｅ作成Ｌ
、既４ ＝ｙテｙクスレコードオカレンスと論理順序と
を保証している。したがって、Ｂ＋トリー構造をもつ従
来のインデックスでの母集団のレコード群の件数に比例
してインデックスを構成しているノードが増加し、重複
キー値をもつ件数が増加してもインデックスオカレンス
の個数が減らないという欠点があった。
（発明の目的）
本発明の目的は、レコードオカレンスの有するキー値ト
＋レコードオカレンスがデータベースに格納されている
アドレス相互の関係とを考慮してインデックスレコード
オカレンスの形式を決定スることによって上記の欠点を
除去し、インデックス自身の記録容量を削減し、しかも
高速に目的とするレコードオカレンスをアクセスするこ
とができるように構成したインデックス管理方式を提供
することにある。
＋レコードオカレンスがデータベースに格納されている
アドレス相互の関係とを考慮してインデックスレコード
オカレンスの形式を決定スることによって上記の欠点を
除去し、インデックス自身の記録容量を削減し、しかも
高速に目的とするレコードオカレンスをアクセスするこ
とができるように構成したインデックス管理方式を提供
することにある。
（発明の構成）
本発明によるインデックス管理方式は複数個のキーイ１
ｂと、それぞれ前記複数個のキー値の一つをそれぞす１
含む複数個のレコードオカレンスのアドレスとから成る
インデックスレコードオカレンスを生成して保守するイ
ンデックス管理方式において、インデックス生成手段と
、ファイル手段と。
ｂと、それぞれ前記複数個のキー値の一つをそれぞす１
含む複数個のレコードオカレンスのアドレスとから成る
インデックスレコードオカレンスを生成して保守するイ
ンデックス管理方式において、インデックス生成手段と
、ファイル手段と。
インデックス保守手段とを具備して構成したものである
。
。
インデックス生成手段は、一対のキー値と関連アドレス
とから成る第１のタイプのインデックスレコード形式と
、複数個のキー値と、それぞれ複数個のキー値の一つを
それぞれ含む複数個のレコードオカレンスのアドレスと
を示すための１個以上のビットマツプアイテムから成る
第２のタイプのインデックスレコード形式とを備え、イ
ンデックス生成時に同一のキー値を有する複数個のイン
デックスレコードオカレンスの個数ヲ調へ、あらかじめ
定められた基準値と比較し、上記個数が上記基準値以内
の場合には第１のタイプのインデックスレコード形式を
選択し、上記基準値を越えた場合には旭２のタイプのイ
ンデックスレコード形式を選択してインデックスを生成
するだめのものである。
とから成る第１のタイプのインデックスレコード形式と
、複数個のキー値と、それぞれ複数個のキー値の一つを
それぞれ含む複数個のレコードオカレンスのアドレスと
を示すための１個以上のビットマツプアイテムから成る
第２のタイプのインデックスレコード形式とを備え、イ
ンデックス生成時に同一のキー値を有する複数個のイン
デックスレコードオカレンスの個数ヲ調へ、あらかじめ
定められた基準値と比較し、上記個数が上記基準値以内
の場合には第１のタイプのインデックスレコード形式を
選択し、上記基準値を越えた場合には旭２のタイプのイ
ンデックスレコード形式を選択してインデックスを生成
するだめのものである。
ファイル手段は、生成したインデックスをランダムアク
セス可能に記憶するだめのものである。
セス可能に記憶するだめのものである。
インデックス保守手段は、生成したインデックスに対し
てレコードオカレンスの更新処理、あるいは追加処理に
伴ってキー値を変更する場合に、上記画処理と同期して
上記処理に関連したインデックスレコードオカレンスを
変更し、インデックス生成手段による上記基準値に対す
る比較と選択との過程に制御を渡すためのものである。
てレコードオカレンスの更新処理、あるいは追加処理に
伴ってキー値を変更する場合に、上記画処理と同期して
上記処理に関連したインデックスレコードオカレンスを
変更し、インデックス生成手段による上記基準値に対す
る比較と選択との過程に制御を渡すためのものである。
（実施例）
次に、本発明について図面全参照して詳細に説明する。
大容量のデータを持っているデータベース管理システム
において、データベースの中から目的とするレコードオ
カレンスを高速に検索できることは重要である。例えば
、オンライン・リアルタイム環境下で使用しているエン
ドユーザに対して強力な機能を含んだエンドユーザ言語
の提供が盛んである。エンドユーザが作成する問い合わ
せ処理では、単−条件力・ら複合昏１件まで含み、且つ
、試行錯誤的に行う非定型処理が中心であり、最終的に
期待する処理結果の件ｖｉは母集団の容量とはほとんど
無（す、ｊ係に高々数十性までである。よって、これ以
上の件数なイｎた場合には、さらに、灸件値を強く与え
ていたシ、さらに別な観点からや件を与えながら再度く
り返す。このような処理を想定した時、インデックスを
使うことによってアクセス効率向上を計るととｉｒ必須
であシ、データ特性を加味した本発明のインデックス方
式を使うことに、虹って一層の効果がＪｊｌ待できる。
において、データベースの中から目的とするレコードオ
カレンスを高速に検索できることは重要である。例えば
、オンライン・リアルタイム環境下で使用しているエン
ドユーザに対して強力な機能を含んだエンドユーザ言語
の提供が盛んである。エンドユーザが作成する問い合わ
せ処理では、単−条件力・ら複合昏１件まで含み、且つ
、試行錯誤的に行う非定型処理が中心であり、最終的に
期待する処理結果の件ｖｉは母集団の容量とはほとんど
無（す、ｊ係に高々数十性までである。よって、これ以
上の件数なイｎた場合には、さらに、灸件値を強く与え
ていたシ、さらに別な観点からや件を与えながら再度く
り返す。このような処理を想定した時、インデックスを
使うことによってアクセス効率向上を計るととｉｒ必須
であシ、データ特性を加味した本発明のインデックス方
式を使うことに、虹って一層の効果がＪｊｌ待できる。
以下、駿、１図とｆ４Ｌ２図とを参照しながら説明する
。
。
第１図において、イ／ｊツクス會作成する場合には、第
２図の第２のタイプのインデックスレコード形式のビッ
トマツプアイテム長（ＬＢ）全バイト単位で与える。例
えは、ＬＢ＝３２とすれば１１固のピントマツプアイテ
ム（３２バイト）で、最大２５６個（３２Ｘ ８ ）の
レコードオカレンス會管理することか可能である。ＬＢ
の値はインデックスごとに変更可能であるため、対象キ
ー値の特性をそれぞれ反映できる。
２図の第２のタイプのインデックスレコード形式のビッ
トマツプアイテム長（ＬＢ）全バイト単位で与える。例
えは、ＬＢ＝３２とすれば１１固のピントマツプアイテ
ム（３２バイト）で、最大２５６個（３２Ｘ ８ ）の
レコードオカレンス會管理することか可能である。ＬＢ
の値はインデックスごとに変更可能であるため、対象キ
ー値の特性をそれぞれ反映できる。
次にインデックスオカレンスを作成するために〔キー値
＋レコード相対番号〕を集め、キー値順にソートして与
える。これらの入力データを使ってキー値を調べながら
、インテックス本体のファイル装置芥１が最少となるよ
うに、６Ｊ％ ２図に示す第１のタイプ、もしくｈ第２
のタイプのインテックス本体を使い、ファイル装置」二
の相対ファイルへ作成して保持する。インデックスは同
一レコードタイプに複数個作成できるので、初合粂件に
よる検電が行われることを防定し、レコードオカレンス
ノアトレス情’Ａ Ｉ’ｌ： データベース管理システ
ムが内部的に生成したレコード相対番号を使用している
。この理由は、上記のような複合条件を解決する場合に
、インデックス上のデータを使った訓理演算をビット演
算へ効果的ｔｉｃ置き換えるためである。
＋レコード相対番号〕を集め、キー値順にソートして与
える。これらの入力データを使ってキー値を調べながら
、インテックス本体のファイル装置芥１が最少となるよ
うに、６Ｊ％ ２図に示す第１のタイプ、もしくｈ第２
のタイプのインテックス本体を使い、ファイル装置」二
の相対ファイルへ作成して保持する。インデックスは同
一レコードタイプに複数個作成できるので、初合粂件に
よる検電が行われることを防定し、レコードオカレンス
ノアトレス情’Ａ Ｉ’ｌ： データベース管理システ
ムが内部的に生成したレコード相対番号を使用している
。この理由は、上記のような複合条件を解決する場合に
、インデックス上のデータを使った訓理演算をビット演
算へ効果的ｔｉｃ置き換えるためである。
本方式で、第１の夕／１７のインデックスレコード形式
と、第２のタイプのインデックスレコード形式との切分
けの基準は次のとおりである。
と、第２のタイプのインデックスレコード形式との切分
けの基準は次のとおりである。
■ −意のキー値をもつレコー ドオカレンスは、第１
のタイプのインデックスレコード形式とする。
のタイプのインデックスレコード形式とする。
■ 重複キー値をもつレコードオカレンスの相対レコー
ド番号の関係が第３図の内容を満足する場合には、第２
のタイプのインデックスレコード形式とする。
ド番号の関係が第３図の内容を満足する場合には、第２
のタイプのインデックスレコード形式とする。
ここで、Ｎ個のレコード相対番号の変位が１、Ｂｘ ｓ
以内ならば１個のピ・ノドマツプアイテムでよ＜、ＬＢ
Ｘ８以上ならば複数個のピットマツプアイテムとするか
、あるいはＬＢ長を大きくすることが可能である。
以内ならば１個のピ・ノドマツプアイテムでよ＜、ＬＢ
Ｘ８以上ならば複数個のピットマツプアイテムとするか
、あるいはＬＢ長を大きくすることが可能である。
重初キー値を持っているが第３図の内容を満足しない場
合は、第１のタイプのインデックスレコード形式とする
。
合は、第１のタイプのインデックスレコード形式とする
。
インデックスを作成した後、レコードオカレンスの追加
と更新の処理が行われてキー値が変更された場合につい
ても、上記基準によってタイプＩとタイプ■との変換保
守が実施される。
と更新の処理が行われてキー値が変更された場合につい
ても、上記基準によってタイプＩとタイプ■との変換保
守が実施される。
第１図において、破線はキー値を与え、与えた５
キー値と比較して一致条件満足されるレコード相対番号
を得る場合である。
を得る場合である。
上記方式では、インデックスごとに独立した特性を持た
せることができるだめ、利用効果は非常に大きい。
せることができるだめ、利用効果は非常に大きい。
（発明の効果）
以上説明したように本発明では、重複キー値を持つイン
デックスにより大巾なインデックス記録容量を削減でき
、内容検索処理時にインデックスレコードオカレンスを
アクセスする回斂（物理と論理入出力回斂）が減少する
ので、処理効率が向上するという効果がある。
デックスにより大巾なインデックス記録容量を削減でき
、内容検索処理時にインデックスレコードオカレンスを
アクセスする回斂（物理と論理入出力回斂）が減少する
ので、処理効率が向上するという効果がある。
第１図は、インデックス管理方式の概要を示す概略図で
ある。 第２図は、第１図のインデックス管理方式によシ生成さ
れ、保守されるインデックスオカレンスの概略を示す図
である。 １−１・・・ビットマツプアイテム長 １−２・・・キー値と１コ一ド相対番号特許出願人 日
本電気株式会社 代理人 弁理士 井 ノ ロ ′ 壽 牙１図 （二二二＝＝）： 入力・出力値
ある。 第２図は、第１図のインデックス管理方式によシ生成さ
れ、保守されるインデックスオカレンスの概略を示す図
である。 １−１・・・ビットマツプアイテム長 １−２・・・キー値と１コ一ド相対番号特許出願人 日
本電気株式会社 代理人 弁理士 井 ノ ロ ′ 壽 牙１図 （二二二＝＝）： 入力・出力値
Claims (1)
- 複む個のキー値と、それぞれ前記複数個のキー値の一つ
をそれぞれ含む複数個のレコードオカレンスのアドレス
とから成るインデックスレコードオカレンスを生成して
保守するように構成したインデックス管理方式において
、一対のキー値と関連アドレスとプハら成る第１のタイ
プのインデックスレコード形式と、前記複数個のキー値
と、それぞノ１前記複数個のキー値の一つをそれぞれ含
む複ｅ個のレコードオカレンスのアドレスとを示すため
の１個以上のピントマツプアイテム力）ら成る第２のタ
イプのインデックスレコード形式とを備え、インデック
ス生成時に同一のキー値を有する複数個のインデックス
レコードオカレンスの個数Ｋｌべ、ｈらかしめ定められ
た基準値と比較し、前記個数が前記基準値以内の場合に
は前記第１のタイプのインデックスレコード形式を選択
し、前記基°準備を越える場合には前記第２のタイプの
インデックスレコード形式を選択してインデックスを生
成するためのインデックス生成手段と２前記生成したイ
ンデックスをランダムアクセス可能に記憶するためのフ
ァイル手段と、前記生成したインデックスに対して前記
レコードオカレンスの更新処理あるいは追加処理に伴っ
て前記キー値を変更する場合に、前記画処理と同期して
前記処理に関連したインデックスレコードオカレンスヲ
変更し、前記インデックス生成手段による前記基準値に
対する前記比較と前記選択との過程に制御を渡すだめの
インデックス保守手段と？具備して構成したことを特徴
とするインデックス管理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59037074A JPS60181849A (ja) | 1984-02-28 | 1984-02-28 | インデツクス管理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59037074A JPS60181849A (ja) | 1984-02-28 | 1984-02-28 | インデツクス管理方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS60181849A true JPS60181849A (ja) | 1985-09-17 |
Family
ID=12487403
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59037074A Pending JPS60181849A (ja) | 1984-02-28 | 1984-02-28 | インデツクス管理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS60181849A (ja) |
-
1984
- 1984-02-28 JP JP59037074A patent/JPS60181849A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CA2367181C (en) | Method for extracting information from a database | |
| CN108205577B (zh) | 一种数组构建、数组查询的方法、装置及电子设备 | |
| EP1352339B1 (en) | Method of querying a structure of compressed data | |
| EP1360616B1 (en) | Database system and query optimiser | |
| US12505096B2 (en) | Translation of tenant identifiers | |
| EA007209B1 (ru) | Способ управления ключами в базе данных, база данных и способ организации базы данных | |
| CN115114293B (zh) | 一种数据库索引的创建方法、相关装置、设备及存储介质 | |
| CN118797106A (zh) | 一种构建基于树结构的世界状态的方法及计算机设备 | |
| AU2019350694B2 (en) | Identification of records for post-cloning tenant identifier translation | |
| CN119202066B (zh) | 一种数据透视表数据展开方法及装置 | |
| CN110825747B (zh) | 一种信息存取方法、装置和介质 | |
| CN116662019B (zh) | 请求的分配方法、装置、存储介质及电子装置 | |
| KR20160128166A (ko) | 파티션테이블 관리를 수행하는 데이터베이스 및 데이터베이스에서 파티션테이블 관리를 수행하는 방법 | |
| CN114443643B (zh) | 分布式数据库中哈希分布表的实现方法及系统 | |
| US8849866B2 (en) | Method and computer program product for creating ordered data structure | |
| CN114443866B (zh) | 数据处理方法、装置、计算设备及介质 | |
| JPH10240741A (ja) | 木構造型データの管理方法 | |
| JPS62287350A (ja) | インデツクス一括更新方式 | |
| CN116204549A (zh) | 数据查询方法、装置、计算机设备、存储介质和程序产品 | |
| JP2023141215A (ja) | インデックス管理装置 | |
| CN121935252A (zh) | 基于索引对齐的医疗数据重构方法、系统、设备及介质 | |
| CN122019637A (zh) | 一种基于动态位掩码的服务依赖关系高效管理与查询方法 | |
| JPH0762850B2 (ja) | 情報検索装置 | |
| JPS6197743A (ja) | デ−タ管理システム | |
| JPH0253182A (ja) | レコード管理方式 |