(57)【要約】【課題】小さいオーバーヘッドと高いスケーラビリティを有する木構造を探索する方法を提供すること。【解決手段】コンピュータ可読媒体に記憶されたデータの集合を探索するために、木構造を有する索引を用意し、当該データの集合と木構造の葉ノードとを対応させる。葉ノードに双方向リストを有し、内部ノードに一方向リストを有するＢｃ−ｌｉｎｋ木を用い、キーに基づくデータの探索の過程で内部ノードにはロックを実施せず、探索が葉ノードに到達した時点で葉ノードにロックを実施して検索、挿入又は削除の操作を実行する。挿入又は削除においてはメモリバリア命令を利用する。到達した葉ノードにキーに基づくデータが存在しない場合は双方向リストにより連結される他の葉ノードにロックを実施して探索し、前記到達した葉ノードのロックを開放する。【選択図】図１
2010086391.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ可読媒体に記憶されたデータを参照するために、木構造を用いて作成された索引をキーに基づいてたどる方法であって、前記木構造は最上層に１つの根ノード、最下層に少なくとも１つの葉ノードを含み、０個以上の中間の層に前記葉ノードを除く内部ノードを含み、前記葉ノードは２つ以上存在する場合に互いに隣接し得るものとの関係を表す情報を含んで他の葉ノードと双方向に連結し、
前記葉ノードを除く前記木構造に含まれる前記根ノード又は前記内部ノードに対するロック操作を実施することなく、前記木構造に含まれるいずれか１つの階層内で前記キーと関連付け得る前記内部ノード又は前記葉ノードを探索して現在のノードとする探索ステップと、
現在のノードを前記木構造の内部で移動して特定のノードを現在のノードとする移動ステップであって、前記探索ステップにより現在のノードとして特定されるノードが前記葉ノードであれば前記葉ノードを現在のノードとして特定し、さもなければ前記木構造に含まれるエッジをたどって前記葉ノードに到達するまでより下層のノードに現在のノードを移動して、到達した前記葉ノードを現在のノードとして特定する移動ステップと、
前記移動ステップにより現在のノードとして特定される前記葉ノードにロック操作を実施して前記キーに関連付けるステップと、
を含む方法。
【請求項２】
前記内部ノードは、２つ以上存在する場合に他の内部ノードとの関係を表す情報を含んで一方向に連結する、請求項１に記載の方法。
【請求項３】
前記関連付けるステップは、さらに、
前記木構造に含まれる前記内部ノードの階層内で前記キーと関連付け得る内部ノード又は葉ノードを探索する前記ステップにおいて、前記内部ノードの中の要素数を読み込むステップと、
メモリバリア命令を実施するステップと、
前記内部ノードの中で前記読み込んだ要素数の範囲内で前記キーと関連付け得る内部ノード又は葉ノードを探索するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記関連付けるステップは、さらに、
前記移動ステップにより、現在のノードに前記キーと関連付け得る情報が含まれるならば、現在のノードとして特定される前記葉ノードにロック操作を実施して前記キーに関連付けるステップと、
さもなければ前記葉ノードを含む階層において前記キーと関連付け得る他の葉ノードに現在のノードを移動して前記他の葉ノードにロック操作を実施し、前記葉ノードに対するロック操作を解除して前記他の葉ノードを前記キーに関連付けるステップと、
を含む請求項１に記載の方法。
【請求項５】
前記キーは検索キーであり、前記関連付けるステップは前記検索キーに基づく検索の結果を見出すステップを含む、請求項１に記載の方法。
【請求項６】
さらに、前記関連付けるステップにより現在のノードとして特定される前記葉ノードに対して前記データを含むノードを新たな葉ノードとして挿入するステップを含む、
請求項１に記載の方法。
【請求項７】
さらに、前記関連付けるステップにより現在のノードとして特定される前記葉ノードが無効化する場合に隣接する葉ノードの情報を一時的に記憶するステップと、
前記葉ノードのロックを解放するステップと、
前記隣接する葉ノードを現在のノードとして前記無効化する前記葉ノードを削除するステップと、
を含む請求項１に記載の方法。
【請求項８】
さらに、前記関連付けるステップにより現在のノードとして特定される前記葉ノードに書き込みロックを実施するステップと、
前記葉ノードに新規な要素を挿入するための十分な余地があることを確認するステップと、
前記確認するステップの判定が真である場合に前記葉ノードの中に前記新規な要素を挿入するステップと、
前記書き込みロックを開放するステップと、
を含む請求項１に記載の方法。
【請求項９】
さらに前記新規な要素を挿入するステップは、
前記確認するステップの判定が偽である場合に、新たな葉ノードを挿入し、前記新たな葉ノードへのエッジを挿入すべき内部ノードを特定するステップと、
前記内部ノードの中の挿入位置の既存のデータの配置を隣接位置に移動するステップと、
メモリバリア命令を実施するステップと、
前記内部ノードの要素数をインクリメントするステップと、
を含む請求項８に記載の方法。
【請求項１０】
さらに、前記関連付けるステップにより現在のノードとして特定される前記葉ノードに書き込みロックを実施するステップと、
前記特定された前記葉ノードに削除するための十分な要素があることを確認するステップと、
前記確認するステップの判定が真である場合に前記特定された前記要素を削除するステップと、
前記書き込みロックを開放するステップと、
を含む請求項１に記載の方法。
【請求項１１】
さらに前記要素を削除するステップは、
前記確認するステップの判定が偽である場合に、葉ノードを削除し、前記削除された葉ノードへのエッジを削除すべき内部ノードを特定するステップと、
前記内部ノードの中の削除位置より後ろのデータの配置を隣接位置に移動するステップと、
メモリバリア命令を実施するステップと、
前記内部ノードの要素数をデクリメントするステップと、
を含む請求項１０に記載の方法。
【請求項１２】
請求項１から１１のいずれか１項に記載の方法の各ステップを、コンピュータを用いて実行するためのコンピュータプログラム。
【請求項１３】
コンピュータ可読媒体に記憶されたデータを参照するために、木構造を用いて作成された索引をキーに基づいてたどるシステムであって、前記木構造は最上層に１つの根ノード、最下層に少なくとも１つの葉ノードを含み、０個以上の中間の層に前記葉ノードを除く内部ノードを含み、前記葉ノードは２つ以上存在する場合に互いに隣接し得るものとの関係を表す情報を含んで他の葉ノードと双方向に連結し、
前記葉ノードを除く前記木構造に含まれる前記根ノード又は前記内部ノードに対するロック操作を実施することなく、前記木構造に含まれるいずれか１つの階層内で前記キーと関連付け得る前記内部ノード又は前記葉ノードを探索して現在のノードとする探索手段と、
現在のノードを前記木構造の内部で移動して特定のノードを現在のノードとする移動手段であって、前記探索手段により現在のノードとして特定されるノードが前記葉ノードであれば前記葉ノードを現在のノードとして特定し、さもなければ前記木構造に含まれるエッジをたどって前記葉ノードに到達するまでより下層のノードに現在のノードを移動して、到達した前記葉ノードを現在のノードとして特定する移動手段と、
前記移動手段により現在のノードとして特定される前記葉ノードにロック操作を実施して前記キーに関連付ける関連付け手段と、
を含むシステム。
【請求項１４】
コンピュータ可読媒体に記憶されたデータを参照するために、木構造を用いて作成された索引をキーに基づいてたどるシステムであって、前記木構造は最上層に１つの根ノード、最下層に少なくとも１つの葉ノードを含み、０個以上の中間の層に前記葉ノードを除く内部ノードを含み、前記葉ノードは２つ以上存在する場合に互いに隣接し得るものとの関係を表す情報を含んで他の葉ノードと双方向に連結し、前記内部ノードは２つ以上存在する場合に他の内部ノードとの関係を表す情報を含んで一方向に連結し、
前記葉ノードを除く前記木構造に含まれる前記根ノード又は前記内部ノードに対するロック操作を実施することなく、前記木構造に含まれるいずれか１つの階層内で前記キーと関連付け得る前記内部ノード又は前記葉ノードを探索して現在のノードとする探索手段と、
現在のノードを前記木構造の内部で移動して特定のノードを現在のノードとする移動手段であって、前記探索手段により現在のノードとして特定されるノードが前記葉ノードであれば前記葉ノードを現在のノードとして特定し、さもなければ前記木構造に含まれるエッジをたどって前記葉ノードに到達するまでより下層のノードに現在のノードを移動して、到達した前記葉ノードを現在のノードとして特定する移動手段と、
前記移動手段により現在のノードとして特定される前記葉ノードに前記キーと関連付け得る情報が含まれるならば、現在のノードとして特定される前記葉ノードにロック操作を実施して前記キーに関連付け、さもなければ前記葉ノードを含む階層において前記キーと関連付け得る他の葉ノードに現在のノードを移動して前記他の葉ノードにロック操作を実施し、前記葉ノードに対するロック操作を解除して前記他の葉ノードを前記キーに関連付ける関連付け手段と、
を含むシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの探索に木構造を用いる方法に関し、特にコンピュータ可読媒体に記憶されたデータの集合に対して、目的のデータを操作するために木構造を探索する方法に関する。
【背景技術】
【０００２】
従来、コンピュータ上で順序付き集合を表現するために木構造を用いることが知られている（非特許文献１）。木構造はノードとエッジとで表され、ノード同士はエッジにより階層的に関連付けられ、単一のノードからなる木構造の最上層を根ノード、木構造の最下層を葉ノードと呼ぶ。例えば、木構造はデータベースの索引の作成等に頻用され、木構造を用いて表現可能なデータに対して検索、挿入、削除等の操作が行われることが知られている。また、従来、木構造としてＢ木（非特許文献２）、Ｂ木の派生のＢ＋木、また特にメモリ上の木構造として用いられるＴ木（非特許文献３）、スループット及びスケーラビリティ（拡張性の一種であり、特に作業の増大に対応する能力を指す）を改善したＢ−ｌｉｎｋ木（非特許文献４）等が知られている。これらの木構造をコンピュータ装置等から参照する場合に、並行な操作を実現するためにはロックやセマフォ等の同期操作を用い得る。
【０００３】
図１７に、従来技術に係る木構造を例示する。これらの木構造は、当技術分野に公知のノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）又はリンクで表される。ノードには何らかのデータ（値、条件、別のデータ構造、別の木構造）が付属している。例えば該データは大小関係を比較し得る数値又は数値の集合等であり得る。木構造内の各ノードは０個以上の子ノードをもち、子ノードは木構造内では通常は下方に存在する。すなわち、木構造は複数の階層を構成する子ノードを含む。木構造の頂点を根ノード、最底辺を葉ノードとも呼称する。図１７に示す木構造は、ある特定の検索のためのデータ（検索キー又は単にキーとも呼称）を記憶媒体に見出す過程等に用い得る。
【０００４】
図１７（ａ）は従来技術に係るＢ＋木（Ｂ＋Ｔｒｅｅとも呼称）の概念を示すブロック図である。図１７（ａ）の上段には目的のデータが表され、下段にはコンピュータ可読媒体に記憶されているデータの集合が表され、これらの中間に目的のデータをコンピュータ可読媒体から探索するための過程である索引が表される。該索引は例えば条件分岐を含み得る。図１７（ａ）の例においては、目的のデータとして値が「７０」であるデータを可読媒体からＢ木を用いて探索する状況を示す。下段の可読媒体には数値の大小関係に基づいて複数のデータが記憶され得る。まず、上段の目的のデータとして特定の数値等が設定され、探索を開始する。中間の過程において、Ｂ＋木では可読媒体の一部の大小関係を表す索引を用い、目的のデータが特定の索引が表す数値の範囲を下回る場合にはより小さい数値の範囲の索引を用いる等のルールに従って、目的のデータを扱い得る索引を特定する。次いで、目的のデータは、特定の索引が含む大小関係の条件分岐への入力として用いられ得る。この条件分岐の判定の真偽に基づいて、図１７（ａ）の下段に示される可読媒体の中から、目的のデータを含む記憶領域が絞り込まれ、又は特定され得る。
【０００５】
図１７（ｂ）は従来技術に係るＴ木（Ｔ  Ｔｒｅｅとも呼称）の概念を示すブロック図である。図１７（ｂ）に示すＴ木は、当技術分野に公知の二分探索木であり得る。例えば、Ｔ木の全体は、コンピュータ可読媒体に記憶されているデータの全体集合を、数値の大小関係に基づいて複数の部分集合に排他的に分割して構成してもよい。それぞれの部分集合は、数値の境界条件等を索引として含み、境界を連続し得ることに基づいて隣接する他の部分集合との間に連結に関する情報を含んでもよい。目的のデータは、例えば、前順走査、間順走査、又は後順走査等の公知の探索アルゴリズムに従って探索され得る。これにより、目的のデータを含む特定の部分集合が絞り込まれ、又は特定され得る。
【０００６】
図１７（ｃ）は従来技術に係るＢ−ｌｉｎｋ木の概念を示すブロック図である。図１７（ｃ）に示すＢ−ｌｉｎｋ木は、図１７（ａ）に示したＢ木と類似しているが、木構造内の各ノードは、それ自身及び下方の子ノードが持ち得る最大値の情報である「ｈｉｇｈ  ｋｅｙ」を含み得る。図１７（ｃ）においては、各ノードごとの「ｈｉｇｈ  ｋｅｙ」を太線の枠を付して示した。さらに、従来技術に係るＢ−ｌｉｎｋ木においては、同じ階層にあるノードは一方向（例えば図の右方向）に単方向リストで連結し得る。また、ノードが削除された場合には削除されたノードから左隣のノードへｏｕｔｌｉｎｋと呼ばれるポインタが関連付けられる。Ｂ−ｌｉｎｋ木においては、いずれかの特定のノードに対して検索を実施するために該ノードへのロックの獲得及び／又は開放が実施される。
【非特許文献１】フリー百科事典ウィキペディア、「木構造（データ構造）」［online］、平成２０年７月２３日、［平成２０年８月２１日検索］、インターネット、＜URL：http://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)＞
【非特許文献２】R.  Bayer  and  E.  McCreight,  “Organization  and  Maintenance  of  Large  Ordered  Indexes,”  Acta  Informatica,  1,  p.173-189,  1972
【非特許文献３】T.  Lehman  and  M.  Carey,  “A  Study  of  Index  Structures  for  Main  Memory  Database  Management  Systems,”  Proc.  12th  Very  Large  Databases  Conf.,  p.294-303,  1986
【非特許文献４】V.  Lanin  and  D.  Shasha,  “A  Symmetric  Concurrent  B-Tree  Algorithm,”  Proceedings  of  the  Fall  Joint  Computer  Conference,  p.380-389,  1986.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、従来技術又は従来技術の組み合わせにおいては、同期操作は非常にＣＰＵ負荷の大きい、いわゆる「重い」処理であり、特にディスクやネットワークＩ／Ｏを伴わないメモリ上の木構造の場合、同期操作のオーバーヘッドはスループットの低下に直結し、同期操作における競合はスケーラビリティの低下を引き起こしやすかった。すなわち、検索キーに対する処理が高頻度になるほど、頻度に比例する処理結果を得られず、処理の効率は低下していた。これは同時に、膨大化するデータを高速検索するために複数ＣＰＵを並列動作させて処理効率の向上を図ろうとする近年のサーバ装置等を用いても、データベース検索の利用者は十分な利益を受けられないといった問題を生じ得る。また、既存の木構造は読み書きロックを多用するためオーバーヘッドが大きくスケーラビリティが低かった。読み込みロック同士は論理的には競合しないが、読み込みロックを獲得・解放する部分はクリティカルセクションであるため、同じロックオブジェクトに対して頻繁に読み込みロックをかけるとスケーラビリティが低下していた。具体的には、Ｂ木、Ｂ＋木、Ｔ木は操作の間は根ノードに対して読み書きロックを保持し、最大で１回しかロックを取らないためオーバーヘッドは小さいが、必ず単一のロックオブジェクトに対してロックを獲得して解放するためスケーラビリティの低下が発生していた。
【０００８】
本発明は、データベースへのアクセスが高頻度で発生する状況等、データ参照の平行度が増える場合において、小さいオーバーヘッド及び高いスケーラビリティを両立し、これにより高いスループットを実現し得る、木構造を探索する方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、上記課題に鑑み、以下のような解決手段を提供する。なお、本願明細書に用いる用語「ロックを取る」「ロックする」等は、木構造に含まれる任意のノードを特定の処理のためにロック状態とすることを指す。これと反対に、用語「ロックを外す」はロック状態を開放することを指す。コンピュータ可読媒体は磁気、電気、光等の任意の物理化学的手段を用いる可読媒体を含み、読み出し専用でもよく書き込み可能でもよい。コンピュータ可読媒体に記憶される情報の配列は、参照のためのアドレス又は当該情報に関連付けられる任意の数値の大小関係等に従って、例えば左方から右方へ隣接し、又は前方から後方へ隣接するものとして扱う。
【００１０】
本発明による木構造では、木を下降する際に取るロックを最小限にすることで小さいオーバーヘッドと高いスケーラビリティを実現する。発明者は、木構造に含まれる内部ノードに対するロックを取らず、葉ノードに対してだけロックを取る方法の検討により、本発明を完成するに至った。本発明の方法においては、内部ノードに対してロックを取らないことにより、対象とするキー（目的のデータ）を含むべき葉ノード又はその近辺の葉ノードに高速に到達し得る。また、本発明の方法においては、対象とするキーを含まない葉ノードに到達した場合は、ロックを取りながら葉ノードの双方向リストをたどることで、対象とするキーを含むべき葉ノードに到達し得る。ここで本発明に係る双方向リストとは、木構造を構成するエッジ（辺）のうちで隣接する葉ノードの相互の関連付けを表すエッジを指し、より具体的には当該連結により数値範囲の連続性又は数値の大小関係の連続性等を発生可能な隣接する葉ノードの相互の関連付けを指す。双方向リストの関連付けの方向には右向き及び左向きの両者を含む。
【００１１】
一実施形態において、本発明に係る木構造を探索する方法においては、内部ノードにおいて無効なポインタを下降中に読み込まないようにするために、メモリ操作の順序性を制限するＣＰＵ命令であるメモリバリア命令を用い得る。例えば、該メモリバリア命令を用いることにより、本発明に係る方法の実施手段等は、木の下降中に到達したノードに含まれる要素数を読み込んだ後に、ロード・ロードバリアを実行してから該ノードのキーやデータを読み込み得る。一般的にメモリバリア命令はロックよりも軽い操作であり得る。
【００１２】
本発明は、対称型マルチプロセシング、並列コンピューティング、マルチコアマシン、又はこれらの関連技術等の、既存の技術と組み合わせることができ、そのように組み合わせた技術もまた、本発明の技術範囲に含まれる。同様に、本発明の技法を含むデータベースシステム、レプリカ又はミラーリング等を含むフォールトトレラントシステム等も、本発明の技術範囲に含まれる。さらに、本発明の技法は、木構造を探索するための方法の諸段階を、ＦＰＧＡ（現場でプログラム可能なゲートアレイ）、ＡＳＩＣ（特定用途向け集積回路）、これらと同等のハードウェアロジック素子、プログラム可能な集積回路、又はこれらの組み合わせが記憶し得るプログラムの形態、すなわちプログラム製品として提供し得る。具体的には、データ入出力、データバス、メモリバス、システムバス等を備えるカスタムＬＳＩ（大規模集積回路）の形態として、本発明に係る木構造を探索する方法の実施手段、デバイス、組み込み装置等を提供でき、そのように集積回路に記憶されたプログラム製品の形態も、本発明の技術範囲に含まれる。
【発明の効果】
【００１３】
本発明によれば、同期操作に関連するＣＰＵ負荷、従来の読み書きロックを多用する木構造の探索方法に関連するオーバーヘッドの増大等を招かず、小さいオーバーヘッド及び高いスケーラビリティを両立し得るという効果がある。すなわち、本発明の方法においては、実質的に負荷の増大に比例して処理結果を得ることが可能である。従って、複数プロセッサを並列動作させて処理効率を図る近年のサーバ装置構成のメリットを十分に活用し得るデータベース装置等を実現することが可能になる。また、本発明によれば、データベースへのアクセスが高頻度で発生する状況等、データ参照の平行度が増える場合においても高いスループットを実現し得るという効果がある。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態について図を参照しながら説明する。なお、これらはあくまでも一例であって、本発明の技術的範囲はこれらに限られるものではない。
【００１５】
（Ｂｃ−ｌｉｎｋ木の動作条件）
本発明に係る一実施形態は、「Ｂｃ−ｌｉｎｋ木」と呼称する、木構造を探索する方法に関する。この「Ｂｃ−ｌｉｎｋ木」は、実施形態に従って次の特徴を有する。
［特徴１］木の構成として、従来技術に係るＢ−ｌｉｎｋ木の構成に加えて、葉ノードを双方向リストで連結することを含む。
［特徴２］読み込み操作においては木の下降中に内部ノードのロックを取らず、葉ノードの読み込みロックのみを取る。
［特徴３］読み込み操作が対象キーを含まない葉ノードに到達した場合は、読み込みロックを獲得しつつ双方向リストをたどって対象キーを含むべき葉ノードを探索する。
［特徴４］書き込み操作の場合も読み込み操作と同様に内部ノードのロックは取らず、葉ノードの書き込みロックのみを取る。双方向リストをたどる操作も同様である。もし葉ノードの追加・削除が必要であるならばＢ−ｌｉｎｋ木と同じアルゴリズムで再度木の下降からやり直す。
［特徴５］内部ノードへのアクセスの際、無効なデータを読み込まないようにするために、木の下降中は要素数を読み込んだ後でロード・ロードバリアを実行してからキーやデータを読み込む。書き込み操作が内部ノードの中を変更する場合は、キーやデータやｏｕｔｌｉｎｋ（削除等により無効化したノードの左隣のノードに関連付けられるポインタ）を書き込んだ後にストア・ストアバリアを実行してから要素数を書き込む。ロード・ロードバリア及びストア・ストアバリアとしてはＣＰＵ命令に含まれるメモリバリア命令を用い得る。
【００１６】
また、本発明の一実施形態に係るＢｃ−ｌｉｎｋ木においては、根ノードを含む任意の内部ノードから木を下降していずれかの有効な葉ノードに到達さえできれば、双方向リストをたどって目的とする葉ノードに到達し得る。ここで、有効な葉ノードに到達するためには、木の下降中において次の条件を満たすことが必要である。
［条件１］無限ループが無いこと。
［条件２］それ以上先にたどれないノードが無いこと。
［条件３］ヌルポインタを読み込まないこと。
［条件４］すでにメモリ領域が解放されたノードに触らないこと。
【００１７】
前述の条件１及び条件２は、従来技術に係るＢ−ｌｉｎｋ木と共通して、有効な葉ノードに到達するための条件であり得る。条件３に関しては、図１１を用いて後述するように、本発明の一実施形態に係るＢｃ−ｌｉｎｋ木に対する挿入操作であるｉｎｓｅｒｔ＿ｋｅｙ＿ｄａｔａ（）を用いる処理では、未初期化ポインタのｄｏｗｎｌｉｎｋ（より下層のノードに関連付けられるポインタ）が他の処理から参照されることは実質的に発生しない。削除操作ではデータをヌルポインタで上書きする処理は含まないため、同様にｄｏｗｎｌｉｎｋがヌルポインタにはならない。削除操作においてはｏｕｔｌｉｎｋを設定してからストア・ストアバリアを入れるため、ヌルポインタの状態のｏｕｔｌｉｎｋが他の処理から参照されることは発生しない。
【００１８】
本発明による木構造では、木を下降する際に取るロックを最小限にすることで小さいオーバーヘッドと高いスケーラビリティを実現する。具体的には、内部ノードに対するロックは取らず葉ノードに対してだけロックを取る。内部ノードに対してロックは取らないので、対象とするキーを含むべき葉ノード又はその近辺の葉ノードに高速に到達し得る。対象とするキーを含まない葉ノードに到達した場合は、ロックを取りながら葉ノードの双方向リストをたどることで、対象とするキーを含むべき葉ノードに到達し得る。内部ノードにおいて無効なポインタ（ヌルポインタや既にメモリ領域が解放されたノードへのポインタ）を下降中に読み込まないようにするために、ロックよりも軽い操作であるメモリバリア命令を用い得る。
【００１９】
（Ｂｃ−ｌｉｎｋ木の概念）
図１は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の概念を示すブロック図である。一実施形態において、Ｂｃ−ｌｉｎｋ木７００は、従来技術に係るＢ−ｌｉｎｋ木の構造を含む。具体的には、Ｂｃ−ｌｉｎｋ木７００は、根ノード８１０、内部ノード８２０、８３０、葉ノード８４０、８５０、８６０、８７０、８８０、８９０、エッジ７１０、７２０、７４０、７４２、７４４、７４６、７４８、７５０、一方向リスト７３０等からなる木構造である。根ノードを単に根と呼称してもよく、葉ノードを単に葉と呼称してもよい。これらのノードは、根ノード８１０から葉ノード８４０、８５０、８６０、８７０、８８０、８９０に至る階層構造を構成し得る。また、葉ノード又は葉ノードの和は、コンピュータ可読媒体等に記憶されたデータの集合であり得る。図１においては、３層の階層構造を例示するが、本発明に係るＢｃ−ｌｉｎｋ木の階層構造の層数は任意に設定し得る。別の実施形態において、Ｂｃ−ｌｉｎｋ木７００は、さらに上位の階層を有する、より大きなＢｃ−ｌｉｎｋ木の一部であり、根ノード８１０は内部ノードの一部であり得る。また別の実施形態において、Ｂｃ−ｌｉｎｋ木７００は、他のより大きなＢｃ−ｌｉｎｋ木の一部を抜粋したものであり、図示のノードはいずれも内部ノードであり得る。以下の説明においては、根ノード８１０から葉ノード８４０〜８９０に至る動作の諸段階について記載する。
【００２０】
図１に示すＢｃ−ｌｉｎｋ木７００は、従来技術には含まれない、双方向リスト７６０、７６２、７６４、７６６、７６８を含む。これらは、本発明に係るＢｃ−ｌｉｎｋ木７００の特徴である、葉ノード８４０〜８９０を双方向に関連付けるために用い得る。双方向リスト７６０、７６２、７６４、７６６、７６８の詳細な動作については、図９を用いて後述する。
【００２１】
図１に示した例示のＢｃ−ｌｉｎｋ木７００において、各ノードは枠に囲まれた値の数値をデータとして含み得る。例えば、根ノード８１０は、「ｌｏｗ  ｋｅｙ」７０２として数値「７０」を含み、「ｈｉｇｈ  ｋｅｙ」７０４として数値「１４０」を含み得る。図１においては、「ｈｉｇｈ  ｋｅｙ」７０４を太枠で示した。例えば、本発明に係る木構造を探索する方法においては、根ノード８１０はこれらの「ｌｏｗ  ｋｅｙ」７０２又は「ｈｉｇｈ  ｋｅｙ」７０４に基づいて大小関係を判定し得る何らかの数値を検索キーとして受け付け得る。さらに、本発明に係るＢｃ−ｌｉｎｋ木７００においては、階層構造を順次たどることにより、当該検索キーがいずれの葉ノードに含まれるかが見出され得る。
【００２２】
例示的な一実施形態において、本発明に係るＢｃ−ｌｉｎｋ木７００は、根ノード８１０に定義された「ｌｏｗ  ｋｅｙ」７０２又は「ｈｉｇｈ  ｋｅｙ」７０４に基づいて大小関係を判定し得る数値を検索キーとして受け付け得る。例えば、数値「４５」を記憶しているコンピュータ可読媒体の場所を特定するために検索の問い合わせが発生すると、本発明に係るＢｃ−ｌｉｎｋ木７００は、根ノード８１０に定義された「ｌｏｗ  ｋｅｙ」７０２に基づいて当該「ｌｏｗ  ｋｅｙ」７０２よりも小さい値「４５」を検索するために、エッジ７１０をたどり、内部ノード８２０に到達する。次いで、本発明に係るＢｃ−ｌｉｎｋ木７００は、内部ノード８２０に含まれる複数のキーに対する当該数値「４５」の大小関係に基づいて、エッジ７４２をたどり、葉ノード８５０に到達し得る。葉ノード８５０は、「ｌｏｗ  ｋｅｙ」として数値「４０」の情報を含み、「ｈｉｇｈ  ｋｅｙ」として数値「５０」の情報を含み得る。従って、検索の目的である数値「４５」はこの葉ノード８５０に含まれることが見出され得る。他の数値を検索する場合も同様であり、例えばエッジ７２０及びエッジ７５０をたどる検索により、葉ノード８９０に含まれる数値等が見出され得る。
【００２３】
このように動作することにより、本発明に係るＢｃ−ｌｉｎｋ木７００は、Ｂ−ｌｉｎｋ木と同等の階層構造を有することにより、葉ノードが双方向リスト７６０〜７６８で連結される以外はＢ−ｌｉｎｋ木としての動作を実施し得る。検索・挿入・削除等の個別の操作のアルゴリズムについては、それぞれ図４、図５、図６を用いて後述する。
【００２４】
本発明に係るＢｃ−ｌｉｎｋ木においては読み込み操作のために木を下降する際に、内部ノードに対する読み込みロックは全く取らなくてもよい。本発明に係るＢｃ−ｌｉｎｋ木においては、葉ノードに到達するときに、葉ノードに対して読み込みロックを取り、当該葉ノードの内部からキーを探し得る。従って、本発明に係るＢｃ−ｌｉｎｋ木において、あるキーを検索する場合は、当該キーが木の中に存在しかつ他の書き込み操作との競合が無いならば、葉ノードの読み込みロックを１回取るだけで操作は完了する。書き込み操作の場合も、葉ノードの追加もしくは削除が不要ならば、同様のアルゴリズムで葉ノードの書き込みロックを１回取るだけで完了する。葉ノードの追加もしくは削除が必要な場合はＢ−ｌｉｎｋ木と同じアルゴリズムでもう一度木の下降からやり直す。葉ノードの数は非常に多いので、検索・挿入・削除するキーが十分に分散しているならば、複数のスレッドが同一の葉ノードのロックを取ろうとすることはまれである。これにより、本発明に係るＢｃ−ｌｉｎｋ木においては、小さいオーバーヘッドと高いスケーラビリティを実現し得る。
【００２５】
（読み込み操作と書き込み操作の競合）
図２は、本発明の一実施形態に係る、読み込み操作と書き込み操作が内部ノードにおいて競合する場合の処理を例示する図である。この場合、読み込み操作は間違った葉ノードに到達してしまうことがあるが、葉ノード同士の双方向リストをたどることで正しい葉ノードを見つけることができる。
【００２６】
図２（ａ）は、検索操作と挿入操作が競合する例の初期状態を示す図である。全ての木のノードはその中にある要素数を表すフィールドを有してもよい。この例では木の根ノードの要素数は２である。
【００２７】
図２（ｂ）に、最初に検索操作ｓｅａｒｃｈ（ｔｒｅｅ，８０）が木の根ノードの要素数を読み込む例を示す。次に挿入操作ｉｎｓｅｒｔ（ｔｒｅｅ，１０，ｄａｔａ）が行われるとする。ノードの要素数の上限が３であるならば一番左の葉ノードの容量がオーバーし得る。そこで新しい葉ノードが追加され、１つ上の階層のノードにはキーである数値「２０」と新しい葉ノードへのポインタが挿入される。図２（ｃ）に、挿入操作の結果を示す。しかし、検索操作は既に木の根ノードの要素数として２を読み込んでいるため、要素数２の範囲でキーである数値「８０」を検索する。結果として、図２（ｄ）に示すように、キーである数値「８０」を含まない葉ノードに到達してしまう。しかし、葉ノードの中の最大キー値「７０」よりも検索キーである数値「８０」の方が大きいことから、図２（ｅ）に示すように、検索操作は続いて右隣の葉ノードの読み込みロックを獲得して中の検索を実施する。最終的に検索操作はキーである数値「８０」を見出すことができる。
【００２８】
このような読み込み操作及び書き込み操作は、次のような規則に従い得る。
［読み込み規則１］読み込み操作は木の下降中に内部ノードのロックは取らず、葉ノードの読み込みロックのみを取る。
［読み込み規則２］読み込み操作が対象キーを含まない葉ノードに到達した場合は、読み込みロックを獲得しつつ双方向リストをたどって対象キーを含むべき葉ノードを探索する。
［書き込み規則１］書き込み操作の場合も読み込み操作と同様に内部ノードのロックは取らず、葉ノードの書き込みロックのみを取る。双方向リストをたどる操作も同様である。もし葉の追加・削除が必要とわかったならばＢ−ｌｉｎｋ木と同じアルゴリズムで再度木の下降からやり直す。
［書き込み規則２］内部ノードにおいて無効なポインタを読み込まないようにするために、木の下降中は要素数を読み込んだ後でロード・ロードバリアを入れる。書き込み操作が内部ノードを変更する場合はストア・ストアバリアを入れてから要素数を書き込む。
【００２９】
このように動作することにより、本発明に係る木構造を探索する方法においては、読み込み操作と書き込み操作が競合する状況が生じても、それぞれの操作について正しい結果を得ることが可能である。
【００３０】
（検索操作と削除操作の競合）
図３は、本発明の一実施形態に係る、検索操作と削除操作が競合する場合の処理を例示する図である。
【００３１】
図３（ａ）に、検索操作と削除操作とが競合する例の初期状態を示す。図３（ｂ）に、検索操作ｓｅａｒｃｈ（ｔｒｅｅ，８０）が木の根ノードの要素数を読み込んだ時点の状態を示す。図３（ｂ）の時点において、削除操作ｄｅｌｅｔｅ（ｔｒｅｅ，４０）が行われたとする。すると、図３（ｃ）に示すように、従来技術に係るＢ−ｌｉｎｋ木のアルゴリズムに従って葉ノードが削除され、木の根ノードの中の対応するキーである数値「４０」とその右隣のデータも削除される。要素が削除された場合、ノードの中のそれより大きい要素は１つ左へ移動して左詰にされるが、左端の要素もそのまま上書きされずに残される。次いで、図３（ｄ）に示すように、検索操作は要素数＝３として根ノードの中を探索するため左端のデータ（元のキーである数値「７０」の右隣）のポインタを読み込んで下降する可能性があるが、いずれにせよ有効なポインタであるため、キーである数値「８０」を見い出すことができる。
【００３２】
このように動作することにより、本発明に係る木構造を探索する方法のＢｃ−ｌｉｎｋ木は、読み込み操作と書き込み操作が競合する場合にも正しく動作することが可能である。
【００３３】
（データ構造）
本発明の一実施形態に係るＢｃ−ｌｉｎｋ木のノードのデータ構造は、例えば次のような擬似コードを用いて表し得る。
【数１】
2010086391.tif 000003
式中、項目（Ｉ−ａ）は内部ノードと葉ノードを区別するための定義、項目（Ｉ−ｂ）は読み書きロック、項目（Ｉ−ｃ）は要素数、項目（Ｉ−ｄ）は自身と子ノードの中のキーが取り得る最大値、項目（Ｉ−ｅ）は左隣のノード、項目（Ｉ−ｆ）は右隣のノード、項目（Ｉ−ｇ）はこのノードが削除されたときに有効なノードを指すことの定義、項目（Ｉ−ｈ）はキー（検索キー等）の定義、項目（Ｉ−ｉ）はデータ（データの集合又はデータベース等）の定義である。
【００３４】
葉ノードではｌｅｆｔ＿ｓｉｂｌｉｎｇとｒｉｇｈｔ＿ｓｉｂｌｉｎｇとが双方向リストのために用いられる。内部ノードではｒｉｇｈｔ＿ｓｉｂｌｉｎｇとｏｕｔｌｉｎｋがＢ−ｌｉｎｋ木のｒｉｇｈｔｌｉｎｋ、ｏｕｔｌｉｎｋと同様に用いられる。ｏｕｔｌｉｎｋとｌｅｆｔ＿ｓｉｂｌｉｎｇは同時に使われることはないので、同じフィールドにマップすることが可能であり、この場合のメモリ使用量はＢ−ｌｉｎｋ木と同じである。
【００３５】
（Ｂｃ−ｌｉｎｋ木に対する操作）
以下、Ｂｃ−ｌｉｎｋ木に対する１つのキーの検索、挿入、削除操作のアルゴリズムを例示する。ある範囲のキーに対する操作はこれらの基本操作と葉ノード同士の双方向リストの探索の組み合わせで実現し得る。
【００３６】
（検索アルゴリズム）
図４は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の検索操作のアルゴリズムを示すフロー図である。各ステップの動作は次のようになる。
Ｓ１１０：ｓｅａｒｃｈ（ｔｒｅｅ，ｋｅｙ）を開始する。ここで、ｓｅａｒｃｈは検索操作、ｔｒｅｅは検索対象の木構造、ｋｅｙは検索キーである。
Ｓ１２０：ロックを取らずに木を下降する処理であるｌｏｃａｔｅ＿ｌｅａｆ＿ｎｏｌｏｃｋ（）を呼び実行する。
Ｓ１３０：既に削除された葉ノードに到達することがあるので、有効な葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｖａｌｉｄ＿ｌｅａｆ（）を呼んで実行し、さらに葉ノードの読み込みロックも獲得する。
Ｓ１４０：双方向リストをたどってｋｅｙを含むべき葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｂｏｕｎｄｉｎｇ＿ｌｅａｆ（）を呼び実行する。
Ｓ１５０：葉ノードの中でｋｅｙに対応するデータを検索する。
Ｓ１６０：葉ノードの読み込みロックを解放する。
Ｓ１７０：ｋｅｙに対応するデータがあればそれを返し、無ければＮＯＴ＿ＦＯＵＮＤを返して終了する。
【００３７】
これらのステップのうち、ｋｅｙに対応するデータがあればそれを返す操作（Ｓ１７０の一部）は、従来技術に係るＢ−ｌｉｎｋ木における検索操作と共通のステップを用いてもよい。一例として、次式で表されるｓｅａｒｃｈ＿ｆｏｒ＿ｋｅｙ（）を用いてもよい。
【数２】
2010086391.tif 000004
式中、変数ｍａｘには、このｓｅａｒｃｈ＿ｆｏｒ＿ｋｅｙ（）で表される検索操作を呼び出す、本発明に係る方法に含まれる処理により、特定のノードに含まれるデータの個数等が用いられる。
【００３８】
図５は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木のロックを取らずに木を下降するアルゴリズムを示すフロー図である。Ｂｃ−ｌｉｎｋ木のロックを取らずに木を下降する操作は次のようになる。
Ｓ２１０：Ｌｏｃａｔｅ＿ｌｅａｆ＿ｎｏｌｏｃｋ（ｎｏｄｅ，ｋｅｙ）を開始する。ここでｎｏｄｅは操作の対象であるノードを表す変数、ｋｅｙは検索キーである。
Ｓ２２０：現在のノードは葉ノードであるかどうかを判定する。真であればＳ２３０に進み、偽であればＳ２６０に進む。
Ｓ２３０：現在のノードの要素数をレジスタに読み込む。
Ｓ２３５：ロード・ロードバリア命令を実行する。
Ｓ２４０：要素数がゼロであるかどうかを判定する。真であればＳ２５０に進み、偽であればＳ２４５に進む。
Ｓ２４５：ｏｕｔｌｉｎｋをたどって到達したノードを現在のノードとし、Ｓ２３０に進む。
Ｓ２５０：内部ノードの中でｋｅｙを検索し、対応するデータが指すノードを現在のノードとしてＳ２１０に進む。
Ｓ２６０：現在のノードを返して終了する。
【００３９】
図６は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の有効な葉を探すアルゴリズムを示すフロー図である。Ｂｃ−ｌｉｎｋ木の有効な葉を探す操作は次のようになる。
Ｓ３１０：ｓｅａｒｃｈ＿ｆｏｒ＿ｖａｌｉｄ＿ｌｅａｆ（ｌｅａｆ，ｗｒｉｔｅ＿ｌｏｃｋ）を開始する。ここで、ｌｅａｆは操作の対象である葉ノード、ｗｒｉｔｅ＿ｌｏｃｋは書き込みロックを取るか読み込みロックを取るかを示すフラグである。
Ｓ３２０：書き込み操作の場合には現在の葉ノードの書き込みロックを、読み込み操作の場合には読み込みロックを獲得する。
Ｓ３３０：現在の葉ノードの要素数がゼロより多いかどうかを判定する。真であればＳ３７０に進み、偽であればＳ３４０に進む。
Ｓ３４０：現在の葉ノードのｏｕｔｌｉｎｋをレジスタに読み込む。
Ｓ３５０：ロックを解放する。
Ｓ３６０：レジスタに読み込んだｏｕｔｌｉｎｋの指す葉ノードを現在の葉ノードとする。
Ｓ３７０：現在の葉ノードを返して終了する。
【００４０】
（デッドロックの回避）
図７及び図８は、本発明の一実施形態に係る、木構造を探索する方法においてデッドロックを回避する方法を示す図である。
【００４１】
デッドロックは、葉ノード同士の双方向リストの探索で問題となり得る。あるキーが隣同士の２つの葉ノードの間の値であることを確認するためには２つの葉ノードの読み込みロックを同時に獲得する必要がある。一方、後述の挿入や削除操作でも２つ以上の葉ノードの書き込みロックを同時に獲得する必要がある。読み込み操作と書き込み操作とがそれぞれ逆方向から同時にロックを取ろうとするとデッドロックが起きる。
【００４２】
図７（ａ）に、本発明の一実施形態に係るデッドロックを回避する方法を例示する。左の葉ノードをｉｎｓｅｒｔ（ｔｒｅｅ，３０，ｄａｔａ）が書き込みロックし、右の葉ノードをｓｅａｒｃｈ（ｔｒｅｅ，５０）が読み込みロックした状態で互いのロックを獲得しようとしてデッドロックしている。この場合、デッドロックを検出してロック操作のやり直しをすることができる機能がロックにあるならば、その機能を用いることができる。しかしながら、本発明においては、この機能を用いることなく、２つ以上の葉ノードを同時にロックする場合は必ず左から右の順番にロックを獲得することでデッドロックを回避し得る。
【００４３】
図８（ａ）に示すように、本発明の一実施形態に係るデッドロックを回避する方法においては、左から右に葉ノードをたどる場合は右の葉ノードのロックを獲得してから左の葉ノードのロックを解放してもよい。この手法は一般にロックカップリングと呼ばれる。さらに、図８（ｂ）に示すように、これと逆に、右から左にたどる場合は、右の葉ノードのロックを解放してから左の葉ノードのロックを獲得してもよい。
【００４４】
図８を用いて示した方法を、図７に示した方法に適用してもよい。一実施形態において、図７（ｂ）に示すように、ｓｅａｒｃｈ（ｔｒｅｅ，５０）が左方向へ探索するのでまず読み込みロックを解放し、その間にｉｎｓｅｒｔ（ｔｒｅｅ，３０，ｄａｔａ）がキーと新しい葉ノードの挿入操作を終了してもよい。次いで、図７（ｃ）に示すように、ｓｅａｒｃｈ（ｔｒｅｅ，５０）が読み込みロックを獲得して今度は右方向への探索を開始してもよい。右方向への探索にはロックカップリングを用いて同時に２つの葉ノードのロックを取ってもよい。最終的には、この例においては、図７（ｄ）に示す状態に到達することにより、キー５０が木の中に無いことが判明し得る。
【００４５】
このように動作することにより、本発明に係る木構造を探索する方法においては、本発明の特徴である双方向リストにより連結された葉ノードの間で、ロックカップリングを適用することにより、デッドロックを回避し得る。
【００４６】
（双方向リストの利用）
図９は、本発明の一実施形態に係る、木構造に含まれる葉ノード同士の双方向リストをたどるアルゴリズムのフロー図である。双方向リストをたどる手順は、例えば次のようになる。
Ｓ５１０：ｋｅｙが現在の葉ノードのキーの最小値以上であるかどうかを判定する。真であればＳ５４０に進み、偽であればＳ５２５に進む。
Ｓ５２０：左端に到達したかどうかを判定する。真であればＳ５８０に進み、偽であればＳ５３０に進む。
Ｓ５３０：現在の葉ノードのロックを解放する。
Ｓ５３５：左隣の葉ノードへのポインタを引数として、有効な葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｖａｌｉｄ＿ｌｅａｆ（）を呼び、左隣の有効な葉ノードを見つけて現在の葉ノードとする。
Ｓ５４０：ｋｅｙが現在の葉ノードのキーの最大値以下であるかどうかを判定する。真であればＳ５９０に進み、偽であればＳ５４５に進む。
Ｓ５４５：右端に到達したかどうかを判定する。真であればＳ５９０に進み、偽であればＳ５５０に進む。
Ｓ５５０：書き込み操作の場合は右隣の葉ノードの書き込みロックを解除し、現在の葉ノードのロックを解放する。読み込み操作の場合は読み込みロックを獲得する。
Ｓ５５５：現在の葉のロックを開放する。
Ｓ５６０：右隣の葉ノードを現在の葉ノードとする。
Ｓ５８０：現在の葉ノードを返して終了する。
Ｓ５９０：現在の葉ノードを返して終了する。
【００４７】
（Ｂｃ−ｌｉｎｋ木の挿入）
図１０は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の挿入操作の方法を例示するフロー図である。木の挿入操作の手順は次のようになる。
Ｓ６１０：ｉｎｓｅｒｔ（ｔｒｅｅ，ｋｅｙ，ｄａｔａ）を開始する。
Ｓ６１５：ロックを取らずに木を下降する処理であるｌｏｃａｔｅ＿ｌｅａｆ＿ｎｏｌｏｃｋ（）を呼び実行する。
Ｓ６２０：既に削除された葉ノードに到達することがあるので有効な葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｖａｌｉｄ＿ｌｅａｆ（）を呼び実行する。さらに葉ノードの書き込みロックも獲得する。
Ｓ６２５：双方向リストをたどりｋｅｙを含むべき葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｂｏｕｎｄｉｎｇ＿ｌｅａｆ（）を呼び実行する。
Ｓ６３０：葉ノードに十分なスペース（余地）があるかどうかを判定する。真であればＳ６５０に進み、偽であればＳ６４０に進む。
Ｓ６４０：葉ノードの書き込みロックを解放して終了する。
Ｓ６４５：Ｂ−ｌｉｎｋ木のアルゴリズムを用いて木の下降からやり直してｋｅｙとｄａｔａを挿入し、終了する。
Ｓ６５０：葉ノードの中の適切な位置にｋｅｙとｄａｔａとを挿入する。
Ｓ６５５：葉ノードの書き込みロックを解放して終了する。
【００４８】
Ｓ６１０に含まれ、Ｓ６５０において挿入されるｋｅｙ及びｄａｔａは新規でありうる。葉ノードに十分なスペースが無い場合はＢ−ｌｉｎｋ木のアルゴリズムを用いて挿入操作を実施してもよい。従来技術に係るＢ−ｌｉｎｋ木のアルゴリズムと異なる点は、新規な葉ノードを挿入する場合に双方向リストで連結すること、及び内部ノードへのキーとデータの挿入の後にストア・ストアバリアを実行してから要素数を更新することである。
【００４９】
図１１は、本発明の一実施形態に係る、内部ノードのインデックス位置にキー及びデータを挿入する手法を例示するフロー図である。内部ノードのインデックス位置への挿入は、次のように、インデックス位置を挿入位置としてキー及びデータを挿入し、既存のキー及びデータの配置を隣接位置（例えば右隣）に移動して配置し、要素数をインクリメントする（１つ増やす）操作を含む。
Ｓ６６０：ｉｎｓｅｒｔ＿ｋｅｙ＿ｄａｔａ（ｎｏｄｅ，ｉｎｄｅｘ，ｋｅｙ，ｄａｔａ）を開始する。式中、ｎｏｄｅは処理の引数として受け付ける、ノードを表す変数であり、ｉｎｄｅｘは内部ノードのインデックス位置を表す変数である。
Ｓ６６５：葉ノードの中のキー及びデータの配列のｉｎｄｅｘの位置よりも右側の要素を１つ右へずらす。
Ｓ６７０：ｉｎｄｅｘの位置にｋｅｙとｄａｔａを挿入する。
Ｓ６７５：ストア・ストアバリア命令を実行する。
Ｓ６８０：葉ノードの要素数を１増やして終了する。
【００５０】
（Ｂｃ−ｌｉｎｋ木の削除）
図１２は、本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の削除操作の手順を例示するフロー図である。木の削除操作の手順は、次のようになる。
Ｓ８１０：ｄｅｌｅｔｅ（ｔｒｅｅ，ｋｅｙ）を開始する。
Ｓ８２０：ロックを取らずに木を下降する処理であるｌｏｃａｔｅ＿ｌｅａｆ＿ｎｏｌｏｃｋ（）を呼び実行する。
Ｓ８３０：既に削除された葉ノードに到達することがあるので有効な葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｖａｌｉｄ＿ｌｅａｆ（）を呼び実行する。さらに葉ノードの書き込みロックも獲得する。
Ｓ８４０：双方向リストをたどりｋｅｙを含むべき葉ノードを探す処理であるｓｅａｒｃｈ＿ｆｏｒ＿ｂｏｕｎｄｉｎｇ＿ｌｅａｆ（）を呼び実行する。
Ｓ８５０：葉ノードに十分な要素があるかどうかを判定する。真であればＳ８８０に進み、偽であればＳ８６０に進む。
Ｓ８６０：葉ノードの書き込みロックを解放する。
Ｓ８７０：Ｂ−ｌｉｎｋ木のアルゴリズムを用いて木の下降からやり直し、ｋｅｙと対応するデータを削除して終了する。
Ｓ８８０：葉ノードの中からｋｅｙを検索して、もしあればデータと共に削除する。
Ｓ８９０：葉ノードの書き込みロックを解放して終了する。
【００５１】
葉ノードに十分な要素が無い場合はＢ−ｌｉｎｋ木のアルゴリズムを用いて削除操作を実施してもよい。従来技術に係るＢ−ｌｉｎｋ木のアルゴリズムと異なる点は、葉ノードを削除する場合に双方向リストを再び関連付けることと、内部ノードを削除する際にストア・ストアバリアを実行してから要素数を更新することである。なお、当該要素数を更新することは、例えば上述のＳ８５０の判定が偽である場合にＳ８６０の操作に要素数をデクリメントする操作を含めることでもよい。
【００５２】
図１３は、本発明の一実施形態に係る、ノードの要素数がゼロになった場合の削除操作を抜粋して例示する図である。次のＳ９７０における操作は、（１）要素数がゼロになったノードに隣接する（例えば左隣又は前方の）有効なノードに対しては、内部ノードの中の削除位置より後ろ（例えば右隣）のデータの配置を隣接位置（例えば左隣又は前方）に移動する操作であり、又は（２）現在のノードとして特定される葉ノードが無効化する場合に、隣接する葉ノード（例えば右隣又は後方）の情報を一時的に記憶する操作であり得る。
Ｓ９１０：ｎｏｄｅ（処理の引数として受け付ける、ノードを表す変数）の右隣のノードの書き込みロックを獲得する。
Ｓ９２０：Ｂ−ｌｉｎｋ木のアルゴリズムに従って、右隣のノードからｎｏｄｅへキーとデータをコピー。
Ｓ９３０：ｎｏｄｅは葉ノードであるかどうかを判定する。真であればＳ９４０に進み、偽であればＳ９５０に進む。
Ｓ９４０：右隣のノードのさらに右隣のノードの書き込みロックを獲得して双方向リストを再び関連付けてロックを解放する。
Ｓ９５０：右隣のノードのｏｕｔｌｉｎｋをｎｏｄｅにセットする。
Ｓ９６０：ストア・ストアバリア命令を実行する。
Ｓ９７０：右隣のノードの要素数をｎｏｄｅの要素数にコピーし、右隣の要素数は−１にセットする。
Ｓ９８０：右隣のノードのロックを解放して終了する。
【００５３】
Ｂｃ−ｌｉｎｋ木から削除されたノードのメモリ領域はすぐに解放してはならない。なぜならば並行して木を下降中のスレッドから参照されている可能性があるからである。メモリ領域解放の問題は、木構造等のリンク構造に対する細粒度ロックを用いるあらゆる並行アルゴリズムに共通である。従って、本発明に係る木構造を探索する方法においても、従来技術に係るメモリ領域解放の手法を任意に用いてもよい。例えば、Ｂ−ｌｉｎｋ木に対して用いられる、ノードが削除された時刻を記録し、それ以前に開始した木の下降が全て終了した時点で解放可能と判断する手法等を用いてもよい。また、図６を用いて前述したＧＣが利用可能である場合に、これをＢｃ−ｌｉｎｋ木の削除におけるメモリ領域解放のために用いてもよい。
【実施例】
【００５４】
本発明に係るＢｃ−ｌｉｎｋ木のスケーラビリティを確認するために、既存技術であるＢ＋木、Ｂ−ｌｉｎｋ木と本発明Ｂｃ−ｌｉｎｋ木をＣ言語で実装して性能比較を行った。スレッドライブラリとしてｐｔｈｒｅａｄを用い、読み書きロックとしてｐｔｈｒｅａｄ＿ｒｗｌｏｃｋ＿ｔを用いた。単一のキーに対する操作のみ実装し、指定された範囲のキーに対する操作は実装してない。Ｂ−ｌｉｎｋ木とＢｃ−ｌｉｎｋ木とでは、削除されたノードのメモリ領域を解放するアルゴリズムは実装していない。また、メモリ領域の割り当てがボトルネックとならないようにスレッドローカルのヒープを十分に用意した。
【００５５】
実験環境は、オペレーティングシステムにｘ８６＿６４  Ｌｉｎｕｘ  ２．６．１８（レッドハット株式会社）を、ＣＰＵには８コアＸｅｏｎ  １．８６ＧＨｚ（インテル株式会社）をそれぞれ用い、主記憶として８Ｇバイトメモリを用いた。キーは３２ビット整数、データは６４ビットポインタとした。実験ではランダムな１０００万件のキー・データからなる木に対して、ランダムな４０００万回の操作に要する時間を計測してスループットを算出した。当該操作としては「検索８０％、挿入１０％、削除１０％」の割合でそれぞれの操作を含む条件、及び「検索４０％、挿入３０％、削除３０％」の割合でそれぞれの操作を含む条件の２通りの条件を用意して実験した。
【００５６】
表１に、実験で用いたノードサイズとノード内の探索アルゴリズムとを示す。これらのパラメータは８スレッドで検索８０％の実験を行った場合に最高スループットを記録した値を用いている。
【表１】
2010086391.tif 000005
【００５７】
図１４に検索８０％の場合、図１５に検索４０％の場合の結果を示す。従来技術に係るＢ＋木、Ｂ−ｌｉｎｋ木においては処理スレッド数の増加に対してスループットが頭打ちの状態であるのに対し、本発明に係るＢｃ−ｌｉｎｋ木はスレッド数が増えるに従って、実質的にスレッド数に比例してスループットを向上し得る結果が得られた。いずれの実験条件においても、本発明に係るＢｃ−ｌｉｎｋ木においては高いスループットと高いスケーラビリティとを実現し得る。この実験結果から、Ｂｃ−ｌｉｎｋ木は対称型マルチプロセシング、並列コンピューティング、マルチコアマシン等に適した木構造であることが明らかである。
【００５８】
（木構造を探索する装置のハードウェア構成）
図１６は、本発明の一実施形態に係る、木構造を探索する装置のハードウェア構成を示す図である。図１６においては、木構造を探索する装置を情報処理装置１０００とし、そのハードウェア構成を例示する。以下は、コンピュータを典型とする情報処理装置として全般的な構成を説明するが、その環境に応じて必要最小限な構成を選択できることはいうまでもない。
【００５９】
情報処理装置１０００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１０、バスライン１００５、通信Ｉ／Ｆ１０４０、メインメモリ１０５０、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）１０６０、パラレルポート１０８０、ＵＳＢポート１０９０、グラフィック・コントローラ１０２０、ＶＲＡＭ１０２４、音声プロセッサ１０３０、Ｉ／Ｏコントローラ１０７０、ならびにキーボード及びマウス・アダプタ１１００等の入力手段を備える。Ｉ／Ｏコントローラ１０７０には、フレキシブル・ディスク（ＦＤ）ドライブ１０７２、ハードディスク１０７４、光ディスク・ドライブ１０７６、半導体メモリ１０７８等の記憶手段を接続することができる。
【００６０】
音声プロセッサ１０３０には、マイクロホン１０３６、増幅回路１０３２、及びスピーカ１０３４が接続される。また、グラフィック・コントローラ１０２０には、表示装置１０２２が接続されている。
【００６１】
ＢＩＯＳ１０６０は、情報処理装置１０００の起動時にＣＰＵ１０１０が実行するブートプログラムや、情報処理装置１０００のハードウェアに依存するプログラム等を格納する。ＦＤ（フレキシブル・ディスク）ドライブ１０７２は、フレキシブル・ディスク１０７１からプログラム又はデータを読み取り、Ｉ／Ｏコントローラ１０７０を介してメインメモリ１０５０又はハードディスク１０７４に提供する。図１６には、情報処理装置１０００の内部にハードディスク１０７４が含まれる例を示したが、バスライン１００５又はＩ／Ｏコントローラ１０７０に外部機器接続用インタフェース（図示せず）を接続し、情報処理装置１０００の外部にハードディスクを接続又は増設してもよい。
【００６２】
光ディスク・ドライブ１０７６としては、例えば、ＤＶＤ−ＲＯＭドライブ、ＣＤ−ＲＯＭドライブ、ＤＶＤ−ＲＡＭドライブ、ＣＤ−ＲＡＭドライブを使用することができる。この際は各ドライブに対応した光ディスク１０７７を使用する必要がある。光ディスク・ドライブ１０７６は光ディスク１０７７からプログラム又はデータを読み取り、Ｉ／Ｏコントローラ１０７０を介してメインメモリ１０５０又はハードディスク１０７４に提供することもできる。
【００６３】
情報処理装置１０００に提供されるコンピュータプログラムは、フレキシブル・ディスク１０７１、光ディスク１０７７、又はメモリーカード等の記録媒体に格納されて利用者によって提供される。このコンピュータプログラムは、Ｉ／Ｏコントローラ１０７０を介して、記録媒体から読み出され、又は通信Ｉ／Ｆ１０４０を介してダウンロードされることによって、情報処理装置１０００にインストールされ実行される。コンピュータプログラムが情報処理装置に働きかけて行わせる動作は、既に説明した装置における動作と同一であるので省略する。
【００６４】
前述のコンピュータプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としてはフレキシブル・ディスク１０７１、光ディスク１０７７、又はメモリーカードの他に、ＭＤ等の光磁気記録媒体、テープ媒体を用いることができる。また、専用通信回線やインターネットに接続されたサーバシステムに設けたハードディスク又は光ディスク・ライブラリ等の記憶装置を記録媒体として使用し、通信回線を介してコンピュータプログラムを情報処理装置１０００に提供してもよい。
【００６５】
以上の例は、情報処理装置１０００について主に説明したが、コンピュータに、情報処理装置で説明した機能を有するプログラムをインストールして、そのコンピュータを情報処理装置として動作させることにより上記で説明した情報処理装置と同様な機能を実現することができる。
【００６６】
本装置は、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアの組み合わせによる実施では、所定のプログラムを有するコンピュータ・システムでの実施が典型的な例として挙げられる。係る場合、該所定のプログラムが該コンピュータ・システムにロードされ実行されることにより、該プログラムは、コンピュータ・システムに本発明に係る処理を実行させる。このプログラムは、任意の言語、コード、又は表記によって表現可能な命令群から構成される。そのような命令群は、システムが特定の機能を直接実行すること、又は（１）他の言語、コード、もしくは表記への変換、（２）他の媒体への複製、のいずれか一方もしくは双方が行われた後に、実行することを可能にするものである。もちろん、本発明は、そのようなプログラム自体のみならず、プログラムを記録した媒体を含むプログラム製品もその範囲に含むものである。本発明の機能を実行するためのプログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ハードディスク装置、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ可読媒体に格納することができる。係るプログラムは、コンピュータ可読媒体への格納のために、通信回線で接続する他のコンピュータ・システムからダウンロードしたり、他の媒体から複製したりすることができる。また、係るプログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。
【００６７】
以上、本発明を実施形態に則して説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態又は実施例に記載されたものに限定されるものではない。
【図面の簡単な説明】
【００６８】
【図１】本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の概念を示すブロック図である。
【図２】本発明の一実施形態に係る、読み込み操作と書き込み操作が内部ノードにおいて競合する場合の処理を例示する図である。
【図３】本発明の一実施形態に係る、検索操作と削除操作が競合する場合の処理を例示する図である。
【図４】本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の検索操作のアルゴリズムを示すフロー図である。
【図５】本発明の一実施形態に係る、ＢＢｃ−ｌｉｎｋ木のロックを取らずに木を下降するアルゴリズムを示すフロー図である。
【図６】本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の有効な葉を探すアルゴリズムを示すフロー図である。
【図７】本発明の一実施形態に係る、木構造を探索する方法においてデッドロックを回避する方法を示す図である。
【図８】本発明の一実施形態に係る、木構造を探索する方法においてデッドロックを回避する方法を示す図である。
【図９】本発明の一実施形態に係る、木構造に含まれる葉ノード同士の双方向リストをたどるアルゴリズムのフロー図である。
【図１０】本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の挿入操作の方法を例示するフロー図である。
【図１１】本発明の一実施形態に係る、内部ノードのインデックス位置にキー及びデータを挿入する手法を例示するフロー図である。
【図１２】本発明の一実施形態に係る、Ｂｃ−ｌｉｎｋ木の削除操作の手順を例示するフロー図である。
【図１３】本発明の一実施形態に係る、ノードの要素数がゼロになった場合の削除操作を示す図である。
【図１４】本発明の一実施形態に係る、検索８０％の場合における性能比較を示す図である。
【図１５】本発明の一実施形態に係る、検索４０％の場合における性能比較を示す図である。
【図１６】本発明の一実施形態に係る、木構造を探索する装置のハードウェア構成を示す図である。
【図１７】従来技術に係る、木構造を例示する図である。
【符号の説明】
【００６９】
７１０、７２０、７４０、７４２、７４４、７４６、７４８、７５０  エッジ
７３０  一方向リスト
７６０、７６２、７６４、７６６、７６８  双方向リスト
８１０  根ノード
８２０、８３０  内部ノード
８４０、８５０、８６０、８７０、８８０、８９０  葉ノード
１０００  情報処理装置
【図１】
2010086391.tif 000006
【図２】
2010086391.tif 000007
【図３】
2010086391.tif 000008
【図４】
2010086391.tif 000009
【図５】
2010086391.tif 000010
【図６】
2010086391.tif 000011
【図７】
2010086391.tif 000012
【図８】
2010086391.tif 000013
【図９】
2010086391.tif 000014
【図１０】
2010086391.tif 000015
【図１１】
2010086391.tif 000016
【図１２】
2010086391.tif 000017
【図１３】
2010086391.tif 000018
【図１４】
2010086391.tif 000019
【図１５】
2010086391.tif 000020
【図１６】
2010086391.tif 000021
【図１７】
2010086391.tif 000022