TW200834356A - Splitting/connecting method for coupled node tree, and program - Google Patents

Description

200834356 九、發明說明 【發明所屬之技術領域】 本發明，係有關於使用記憶位元列之樹狀的資料構造 ，而從位元列之集合中來檢索出所期望的位元列之檢索方 法者，特別是，係有關於使用有本申請人在日本特願 2006- 1 8 78 27中所提案的耦合節點樹之分割/結合方法及其 程式者。

【先前技術】 近年，社會之資訊化係在進展，而大規模之資料庫亦 成爲被利用在各個領域中。爲了從此種大規模之資料庫而 檢索出記錄，通常係將與各記錄所被記憶之位址附加有對 應關係的記錄內之項目作爲索引鍵並進行檢索，而找出所 期望的記錄。又，在全文檢索中之文字列，亦可看作爲文 章的索引鍵。

而，由於此些之索引鍵係作爲位元列而被表現，因此 資料庫的檢索係可回歸於位元列之檢索。 爲了高速進行上述位元列之檢索，從先前起，即已進 行有對記憶位元列之資料構造所做的各種設計。作爲此些 之其中一例，係周知有所謂的帕翠西雅樹（Patricia tree)之 樹構造。 圖1 ’係爲展示被使用於上述之先前的檢索處理中之 帕翠西雅樹之其中一例者。帕翠西雅樹之節點，係包含有 :索引鍵、檢索鍵之檢查位元位置、左右之連結指標，而 -4- 200834356 被構成。雖並未明示，但是，不用說，在節點中，係被包 含有用以對對應於索引鍵的記錄作存取（a c c e s s )之資訊。 在圖1之例中，保持索引鍵“1 000 1 0”之節點1 750a係 成爲根節點，該檢查位元位置係爲〇。在節點i 75 〇a之左 連結1 7 4 0 a，係被連接有節點1 7 5 0 b，在右連結1 7 4 1 a，係 被連接有節點1 750f。

節點1 7 5 0 b所保持之索引鍵係爲“ 〇 1 〇 〇 1 χ，，，檢查位元 位置20 3 〇b係爲1。在節點1750b之左連結1740b，係被連 接有節點1 750c，在右連結1741b，係被連接有節點1 7 5 0d 。節點1 7 5 0 c所保持之索引鍵係爲“ 〇 〇 〇 1 1丨，，，檢查位元位 置係爲3。節點1 750d所保持之索引鍵係爲“011010”，檢 查位元位置係爲2。 從節點1 7 5 0 c而被連接有實線之部分，係爲表示節點 1 7 5 0 c之左右的連結指標者，未被連接有虛線的左指標 174 0c ’係表示該欄係爲空欄。被連接有虛線之右指標 1 7 4 1 c的虛線之連接目標，係表示指標所展示的位址，在 現在的情況，係表示右指標爲指定節點1 7 5 0 c。 節點1 7 5 0 d之右指標1 7 4 1 d，係指定有節點i 7 5 〇 d本身 ，在左連結1 7 4 0 d，係被連接有節點〗7 5 〇 e。節點1 7 5 0 e所 保持之索引鍵係爲“010010”，檢查位元位置係爲5。節點 1 7 5 0 e之左指標1 7 4 0 e，係指向節點丨7 5 〇 b，右指標1 7 4 1 e ，係指向節點1 7 5 0 e。 又’節點1 7 5 0 f所保持之索引鍵係爲“丨〇丨〇丨丨”，檢查 位元位置173 Of係爲2。在節點175 〇f之左連結174〇f，係 -5- 200834356 被連接有節點1750g，在右連結I741f，係被連接有節點 1750h ° 節點1 7 5 0 g所保持之索引鍵係爲“ 1 〇 〇 〇 1 1 ”，檢查位元 位置1 7 3 0 g係爲5。節點1 7 5 0 g之左指標1 7 4 0 g，係指向節 點1 75 0a，右指標1741g，係指向節點I 750g。

節點1 750h所保持之索引鍵係爲“101100”，檢查位元 位置173 Oh係爲3。節點175 Oh之左指標174 Oh，係指向節 點1 75 0f，右指標1741h，係指向節點l 750h。 於圖1之例中，係以隨著從根節點1 7 5 〇 a而在樹上下 降，各節點之檢查位元位置爲變大的方式而被構成。 當以某一檢索鍵而進行檢索時，係從根節點起而依序 對被保持於各節點之檢索鍵的檢查位元位置作檢查，並進 行關於檢查位元位置之位元値係爲〇或是1的判定，若是爲 1，則到達右連結，若是0,則到達左連結。而後，若是連 結目標之檢查位元位置並未較連結源頭之節點的檢查位元 位置大’亦即是，若是連結目標係並非爲朝向下方而係回 到上方（於圖1中，將以虛線所示之此倒退的連結稱爲退後 連結），則進行連結目標之節點的索引鍵與檢索鍵之比較 。比較之結果，若是相等，則係保證檢索爲成功，若是不 相等’則係保證檢索爲失敗。 如上述所示，在使用有帕翠西雅樹的檢索處理中，雖 然具有：僅需對必要之位元作檢查，即可進行檢索；以及 鍵全體之比較係只需一次即可等的優點，但是亦會有：由 於從各節點必定會分出有2個的連結，因此會使記憶容量 -6- 200834356 增大；或是因爲退後連接之存在所造成的判定處理之複雜 化；因爲必須在藉由退後連結而倒退的情況下才會進行與 索引鍵間之比較所致的檢索處理之延遲；以及在追加、削 除等之資料維護上的困難性等等的缺點。 作爲用以解決此些之帕翠西雅樹的缺點者，例如係有

在下述之專利文獻1中所揭示的技術。在下述之專利文獻1 中所記載的帕翠西雅樹中，係藉由將下位之左右的節點記 憶在連續之區域中，而削減指標之記憶容量，同時，藉由 將用以表示接下來之連結是否爲退後連結的位元設置在各 節點中，而減輕退後連結之判定處理的負擔。 然而，在下述專利文獻1中所揭示者，亦係由於一個 的節點係必定佔據有索引鍵之區域與指標之區域，以及由 於將下位之左右的節點記憶在連續之區域中，而將指標設 爲1個，因此造成就算是在例如圖1所示之帕翠西雅樹的最 下段之左指標1 740c、右指標I741h等的部分，亦需要分 配有與節點相同容量之記憶區域等的原因，而使得記憶容 量之削減效果並不是很大。又，關於因退後連結所致之檢 索處理的延遲問題，或是追加削除等之處理係爲困難的事 態，亦並未被改善。 [專利文獻1]日本特開2001-357 070號公報 【發明內容】 作爲解決上述之先前的檢索手法中之問題點的方法， 本申請人，係在日本特願2 〇 〇 6 - 1 8 7 8 2 7中，提案有一種使 200834356

用有耦合節點樹（c 〇 u p 1 e d η 〇 d e t r e e)之位元列檢索，該耦 合節點樹，係爲由根節點（root node)、與被配置於相鄰接 之記憶區域中的分支節點（branch node)與葉節點（leaf node)、又或是分支節點彼此又或是葉節點彼此之節點對 所成的使用於位元列檢索之樹（tree)，根節點係爲表示樹 之起點的節點，當該樹之節點係爲1個時，係身爲葉節點 ’而當該樹之節點係爲2個以上時，則係爲前述分支節點 ’前述分支節點，係包含有表示進行位元列檢索之檢索鍵 的辨別位元位置、以及連接（link)目標之節點對的其中一 方之節點的位置之資訊，前述葉節點，係包含有由檢索對 象之位元列所成的索引鍵（index key)。 在上述申請中，係展示有：從被給予之索引鍵的集合 中’來產生耦合節點樹之方法，和從耦合節點樹來檢索出 單一的索引鍵之手法等，使用有耦合節點樹之基本的檢索 手法。 又，在位元列之檢索中，係存在有例如求取最大、最 小値，或是求取某範圍內之値等的各種的檢索要求。於此 ，本申請人，係在日本特願2006-293619中，提案了：求 取出親合節點樹之任意的部分木中所包含之索引鍵的最大 値/最小値之手法等。 然而’於近年’隨著資訊處理技術之進展，對資訊服 務的要求亦更加擴大’而成爲更爲嚴格者。在資訊服務之 提供上，成爲基本的’係爲資料庫之建構，以及從該資料 庫中之資訊的取出，但是，積蓄在資料庫中之資料量係曰 -8 - 200834356 益增大，而逐漸成爲極爲巨大者。

本申請人於先前所提案之檢索手法，雖係爲使上述之 逐漸巨大化的資料庫之高速檢索成爲可能者，但是，隨著 資料庫之巨大化的同時，對應於其之耦合節點樹，雖然相 較於習知之樹構造，係可減少記憶容量，然而仍會成爲相 當大。另一方面，在各種記憶手段之記憶容量中，係分別 有其限制，爲了建構較爲經濟的系統，有必要將各種存取 速度、記憶容量之記憶手段作組合而利用之。 又，資料庫本身亦有可能被進行物理性之分割，或是 被分散設置。 故而，係成爲有必要將1個的耦合節點樹作分割、又 或是再結合。 於此，本發明之目的，係在於提供一種：將耦合節點 樹分割爲2個，又或是將2個的耦合節點樹作結合之手法。 若藉由本發明之其中一種實施形態，則係提供一種耦 合節點樹之分割方法，其係指定對成爲分割點之索引鍵所 決定的分割鍵，並求取出處理源頭之耦合節點樹的索引鍵 之最小値或是最大値，並將該些之索引鍵依序削除，直到 到達成爲分割點之索引鍵爲止，將削除後之索引鍵，插入 至處理目標之耦合節點樹中，藉由此，而將耦合節點樹分 割。 又’若藉由本發明之另外一種實施形態，則係在上述 分割方法中，於依序求取處理源頭之耦合節點樹的索引鍵 之最小値或是最大値的處理中，係藉由在上一次之求取出 -9-

200834356 最小値或是最大値時的檢索路徑之履歷，來設 節點而進行之。 又，若藉由本發明之更另外一種實施形態 一種耦合節點樹結合方法，其係將2個的耦合 合，藉由以其中一方之耦合節點樹作爲在上述 之處理源頭並進行削除處理，而將另外一方作 並進行插入處理，而進行之。 又，若藉由本發明之更另外一種實施形態 一種耦合節點樹之分割方法，其係指定對成爲 引鍵作決定之分割鍵，並求取出：身爲處理源 樹之部分樹、且係將分割鍵作爲其之最大値或 之中，身爲最大之部分樹的根節點之分割節點 以前述分割節點作爲根節點之部分樹的分割節 ，藉由此，來產生新的處理目標之耦合節點樹 分割節點樹從前述處理源頭耦合節點樹中削除 又，若藉由本發明之更另外一種實施形態 一種將2個耦合節點樹作結合之方法，其係根 之耦合節點樹的索引鍵之最大値或是最小値、 耦合節點樹的索引鍵之最小値或是最大値，其 分位元位置’來求取出身爲從處理源頭之耦合 分割出來且與處理目標相結合之部分樹的分割 ，並將該分割結合節點樹根據差分位元位置來 之耦合節點樹作結合。 進而’若藉由本發明之更另外一種實施形 定檢索開始 ，則係提供 節點樹之結 分割方法中 爲處理目標 ，則係提供 分割點之索 頭耦合節點 是最小値者 ，而將身爲 點樹作插入 ，並將前述 〇 ，則係提供 據處理源頭 與處理目標 兩者間之差 節點樹而被 結合節點樹 與處理目標 態，則係提 -10- 200834356 供一種程式，其係使電腦實行上述耦合節點樹之分割方法 或是耦合節點樹之結合方法。 若藉由本發明，則能夠以簡單的處理來有效率地實行 耦合節點樹之分割/結合處理，就算是耦合節點樹之大小 變大，亦能使其成爲易於處理者。 【實施方式】

首先，針對由本申請人在先前的上述申請案中所提案 之成爲本發明的前提之耦合節點樹，對將耦合節點樹儲存 於配列中之例作說明。作爲表示分支節點所保持之連結目 標的位置之資料，亦可使用記憶裝置之位址資訊，但是， 藉由使用由可將分支節點或是葉節點之中所佔有的區域之 記憶容量較大者作儲存之配列要素所成的配列，能將節點 之位置以配列號碼來表示，而能削減位置資訊之資訊量。 圖2A ’係爲說明被儲存於配列中之耦合節點樹的構 成例之圖。 若參考圖2A，則節點1〇1係被配置在配列100之配列 號碼1 0的配列要素中。節點1 〇 i，係由節點種類別i 02、辨 別位元位置103以及代表節點號碼1〇4所構成。節點種類別 1 02係爲G，並表示節點1 〇〗係爲分支節點。在辨別位元位 置1 03中，係被儲存有1。在代表節點號碼〗〇4中，係被記 億有連結目標之節點對的代表節點之配列號碼20。另外， 於以下’爲了表記之簡略化，亦有將被儲存於代表節點號 碼中之配列號碼稱爲代表節點號碼的情形。又，亦有將被 -11 - 200834356 儲存於代表節點號碼中之配列號碼，以附加於該節點之符 號或者是附加於節點對之符號來作代表的情況。

在配列號碼20之配列要素中，係被儲存有身爲節點對 111之代表節點的節點[0]112。而，在相鄰接之下一個配 列要素（配列號碼20+ 1)中，係被儲存有與代表節點成爲 一對之節點[1 ] 1 1 3。在節點[0] 1 1 2之節點種類別1 1 4中係被 儲存有0 ;在辨別位元位置1 1 5中係被儲存有3 ;在代表節 點號碼1 1 6中係被儲存有3 0。又，在節點[1 ] 1 1 3之節點種 類別1 1 7中係被儲存有1，而表示節點[1 ] η 3係爲葉節點。 在索引鍵118中，係被儲存有”0001 ”。當然，與針對帕翠 西雅樹而在先前所述相同地，於葉節點中係包含有對與索 引鍵相對應之記錄進行存取的資訊，但是，於表記中係省 略。 另外，將代表節點以節點[〇]來表示，將與其成對之 節點以節點[1]來表示。又，亦有將被儲存於某配列號碼 之配列要素中的節點，稱爲該配列號碼之節點的情況，而 也有將被儲存有節點之配列要素的配列號碼，稱爲節點之 配列號碼的情況。 由被儲存於配列號碼3 0以及3 1之配列要素中的節點 122與節點123所成之節點對121的內容，係被省略。 在被儲存有節點[0] 112、節點[1]1 13、節點122、以及 節點1 2 3的配列要素中分別被附加的〇或是1，係爲在以檢 索鍵來進行檢索的情況時，用以表示對節點對之何一節點 作連結。將在前段之分支節點的辨別位元位置中之檢索鍵 -12- 200834356 的位元値〇或是1，加到代表節點號碼上，並對此配列號碼 之節點作連結。 故而’藉由在前段之分支節點的代表節點號碼上，再 加上檢索鍵之辨別位元位置的位元値，而能求取出連結目 標之節點所被儲存之配列要素的配列號碼。

另外，在上述之例中，係採用節點對之被配置的配列 號碼中之較小的一方作爲代表節點號碼，但是，不用說， 亦可採用較大的一方。 圖2Β，係爲將耦合節點樹之樹狀構造作槪念展示的圖 。圖示之6位元的索引鍵，係與圖1所例示之帕翠西雅樹者 相同。 符號210a所示，係爲根節點。於圖示之例中，根節 點210a係作爲被配置於配列號碼220中之節點對201a的代 表節點。 作爲樹狀構造，於根節點2 1 Oa之下方係配置有節點 對201b，而於其下層係配置有節點對201c與節點對201f， 在節點對201f之下層，係被配置有節點對20 lh與節點對 2〇lg。在節點對201c之下方係被配置有節點對201d，並 更進而在其下方被配置有節點對2 0 1 e。 被附加在各節點之前的〇或是1的符號，係與於圖2 A 中所說明之被附加在配列要素之前的符號相同。因應於檢 索鍵之辨別位元位置的位元値而探索樹，並找出檢索對象 之葉節點。 在圖示之例中，根節點2 1 0 a之節點種類別2 6 0 a係爲0 -13- 200834356 ，表示其係爲分支節點，而辨別位元位置230a係顯示〇。 代表節點號碼係爲220a，此係爲儲存有節點對201b之代 表節點2 1 Ob的配列要素之配列號碼。

節點對201b係以節點210b與21 lb所構成，此些之節 點種類別260b、261b係均爲0，而表示其係爲分支節點。 在節點210b之辨別位元位置230b，係被儲存有1，在連結 目標之代表節點號碼中，係被儲存有節點對20 1 c之代表 節點210c所被儲存之配列要素的配列號碼220b。 在節點210c之節點種類別260c中，由於係被儲存有1 ’因此此節點係爲葉節點，故而，係包含有索引鍵。在索 引鍵2 5 0 c中，係被儲存有“ 〇 〇 〇 1 1 1，，。另一方面，節點2 1 1 c 之節點種類別26 1 c係爲〇，辨別位元位置23 1 c係爲2，在 代表節點號碼中，係被儲存有節點對20 1 d之代表節點 2 1 0d所被儲存之配列要素的配列號碼22〗c。 節點210d之節點種類別260d係爲〇，辨別位元位置 2 3 0 d係爲5，在代表節點號碼中，係被儲存有節點對2 〇 j e 之代表節點21 0e所被儲存之配列要素的配列號碼22〇d。 與節點2 1 0 d成對之節點2 1 1 d的節點種類別2 6 1 d係爲1， 在索引鍵251d中，係被儲存有“〇11〇1〇”。 節點對201e之節點21〇e、21 le的節點種類別260e、 26 1 e係均爲1 ’表示其雙方均爲葉節點，而在各別的索引 鍵250e、251e中，作爲索引鍵，係被儲存有“〇1〇〇1〇，，和 “ 0 1 0 0 1 1，，〇 在身爲節點201b之另外一方的節點211b之辨別位元 -14- 200834356 位置23 1 b，係被儲存有2，在連結目標之代表節點號碼中 ，係被儲存有節點對201f之代表節點21 Of所被儲存之配 列要素的配列號碼2 2 1 b。

節點對201f之節點210f、211f的節點種類別260f、 261f係均爲0，表示其雙方均爲分支節點。在各別之辨別 位元位置23 Of、23 If中，係被儲存有5、3。在節點210f 之代表節點號碼中，係被儲存有節點對201g之代表節點 2 1 0 g所被儲存之配列要素的配列號碼2 2 0 f，在節點2 1 1 f 之代表節點號碼中，係被儲存有身爲節點對20 lh之代表 節點的節點[0]21 lh所被儲存之配列要素的配列號碼221f 節點對201 g之節點210g、21 lg的節點種類別260g、 261g係均爲1，表示其雙方均爲葉節點，而在各別的索引 鍵 2 5 0 g、2 5 1 g 中，係被儲存有 “ 1 〇 〇 〇 1 〇 ” 和 “ 1 〇 〇 〇 1 1，’。 又，同樣的’身爲節點對20 lh之代表節點的節點 [0]210h、與和其成對之節點[l]211h的節點種類別260h、 26 lh係均爲1，表示其雙方均爲葉節點，而在各別的索引 鍵 250h、25 lh 中，係被儲存有 “1 〇1 〇1 1”和 “1 〇 1 1 〇〇”。 以下，針對從上述之樹中對索引鍵“1 000 1 0”作檢索的 處理之流程作簡單說明。辨別位元位置，係設爲從左起而 爲 0、1、2、…。 首先，將位元列“ 1 0001 0”作舉檢索鍵，而從根節點 210a起開始進行處理。根節點210a之辨別位元位置23〇a 由於係爲〇，因此若是檢查檢索鍵“1 000 1 0”之辨別位元位 -15- 200834356 置〇的位元値，則發現其係爲1。於此，對將儲存有代表節 點號碼之配列號碼220a中加上1之後的配列號碼之配列要 素中所儲存的位元2 1 1 b作連結。在節點2 1 1 b之辨別位元 位置23 1 b中，由於係被儲存有2，因此，若是檢查檢索鍵 “10001 0”之辨別位元位置2處的位元値，則發現其係爲0， 故而，對儲存有代表節點號碼之配列號碼22 1 b的配列要 素中所儲存之節點2 1 Of作連結。

在節點210f之辨別位元位置230f中，由於係被儲存 有5，因此，若是檢查檢索鍵“ 1 000 1 0”之辨別位元位置5的 位元値，則發現其係爲〇，故而，對代表節點號碼之被儲 存的配列號碼220f之配列要素中所儲存的節點21 0g作連 結。 由於節點210g之節點種類別260g係爲1 ’而代表其係 爲葉節點，因此，將索引鍵25 0g讀出，並與檢索鍵作比 較，其結果，兩者係均爲“ 1 000 1 0”，而爲一致。如此地， 進行使用有耦合節點樹之檢索。 接下來，參考圖2B，並針對耦合節點樹之構成的意義 作說明。 耦合節點樹之構成，係藉由索引鍵之集合而被規定。 在圖2 B之例中，根節點2 1 0 a之辨別位元位置爲0的原因， 係因爲在圖2B中所例示之索引鍵中，具備有第〇位元爲〇 者以及爲1者之故。第〇位元爲〇之索引鍵的群組，係被分 類至節點2 1 Ob之下，而第〇位元爲1之索引鍵的群組，係 被分類至節點2 1 1 b之下。 -16- 200834356 節點21 lb之辨別位元位置爲2的原因，係因爲其係反 映有：在節點21 lh、210h、21 lg、210g中所儲存之第0位 元爲1的索引鍵，其第1位元係全部等於〇，而爲在第2位元 才開始有所不同者一般之索引鍵的集合之性質之故。 以下’與第〇位元的情況相同地，第2位元爲丨者，係 被分類至節點2 1 1 f側，而第2位元爲0者，則被分類至節 點21 Of側。

而，第2位元爲1的索引鍵，由於係爲從第3位元而開 始有所不同者，因此在節點2 1 1 f之辨別位元位置中，係 被儲存有3，而在第2位元爲0的索引鍵中，由於其第3位元 與第4位元均爲相等，而從第5位元才開始有所不同，因此 ，節點2 1 Of之辨別位元位置中，係被儲存有5。 在節點211f之連結目標中，由於第3位元爲1者與爲0 者係分別各只有1個，因此節點21 Oh、21 lh係成爲葉節點 ，並分別在索引鍵25 Oh與251h中被儲存有‘101011，與 ‘101100’ 〇 就算假設在索引鍵之集合中，替代“101100”而被包含 有“101 101”或是“101110”，亦由於其之到第3位元爲止係 與“101 100”相等，因此僅會使被儲存在節點21 lh中之索 引鍵改變，而不會使樹狀構造之本身改變。但是，若是除 了 “ 1 0 1 1 0 0 ”之外，再加上亦包含有“ 1 0 1 1 0 1 ”，則節點2 1 1 h 係成爲分支節點，而其辨別位元位置係成爲5。若是所追 加之索引鍵係爲“ 1 〇 111 〇”，則辨別位元位置係成爲4。 如以上所說明一般，耦合節點樹之構造，係藉由被包 -17- 200834356 含於索引鍵之集合中的各索引鍵之各位元位置的位元値而 被決定。 而，若更進一步作說明，則由於在每一成爲相異位元 値之位元位置處，均分歧有位元値爲“1”之節點與位元値 爲“〇”之節點，因此，若是以節點[1]側與樹之深度方向爲 優先而探索葉節點，而於該些中所儲存之索引鍵，係成爲 節點21 lh之索引鍵251h的“101 100”、節點210h之索引鍵

250h 的“101011”.....節點210c 之索引鍵250c 的 “000111”，而被以降順來排序。 亦即是，在耦合節點樹中，索引鍵係被排序而配置在 樹上。 當以檢索鍵來作檢索時，則係成爲探索索引鍵之在耦 合節點樹上所被配置之路徑，例如，若是檢索鍵係爲 “101 100”，則係能到達節點21 lh。又，從上述之說明，可 以想像到，就算是當使用“ 1 〇 11 〇 1 ”或是“ 1 0 1 1 1 0 ”來作爲檢 索鍵的情況時，亦會到達節點2 1 1 h，但是，藉由將其與索 引鍵25 lh作比較，檢索會成爲失敗。 又，就算是在例如以“1 001 00”來作檢索的情況時，亦 由於在節點210a、21 lb、21 Of的連結路徑中檢索鍵的第3 位元與第4位元係不會被使用’且“1 001 00”的第5位元係爲 〇，因此係和以“ 1 0001 〇”來檢索的情況時相同，而成爲到 達節點210g。如此這般，係成爲使用因應於被儲存在耦合 節點樹中之索引鍵的位元構成之辨別位元位置而進行分歧 -18- 200834356 圖3 ’係爲說明用以實施本發明之硬體的構成例之圖

本發明之檢索裝置所致的檢索處理以及資料維護，係 藉由至少具備有中央處理裝置3 02以及快取記憶體3 03的資 料處理裝置301，並使用資料儲存裝置308而被實施。資料 儲存裝置3 08，係具備有：耦合節點樹所被配置之配列309 、以及記憶有在檢索中所經過之節點所被儲存的配列要素 之配列號碼的探索經路堆疊3 1 0，該資料儲存裝置3 0 8，係 可藉由主記憶裝置3 05又或是外部記憶裝置3〇6而實現，或 者是’亦可使用經由通訊裝置307而被連接之被配置在遠 方的裝置。 在圖3之例示中，主記憶裝置3 05、外部記憶裝置306 以及通訊裝置3 0 7 ’雖係藉由一條的匯流排3 〇 4而被連接於 貝料處理裝置301 ’但是’連接方法係並不限定於此。又 ’亦可將主記憶裝置305設爲在資料處理裝置301內者，且 亦可將探索路徑堆疊310作爲中央處理裝置302內之硬體而 實現之。或者是，不用說，亦可使外部記憶裝置306具有 配列3 0 9，或是使主記憶裝置3 0 5具備有探索路徑堆疊3 1 〇 等，而因應於可使用之硬體環境、索引鍵集合之大小等， 來適宜地對硬體構成作選擇。 又，雖然並未特別圖示，但是，當然地，爲了將在處 理途中所得到的各種値使用於其後之處理中，故因應於各 個處理，會暫時使用到記憶裝置。 接下來，藉由參考圖4〜圖11B，在爲了理解本發明所 -19-

200834356 需要之範圍內，對在上述之申請中，由本申請 使用有耦合節點樹之基本的檢索處理、在耦合 插入削除處理、以及求取出在耦合節點樹中所 鍵的最大値/最小値之處理等的應用處理之一 圖4，係爲展示在身爲本申請人所致之申 本特願2006-29361 9中所提案之位元列檢索的 流程圖。 首先，在步驟S401中，取得檢索開始節 碼。對應於所取得之配列號碼的配列，係爲儲 節點樹之任意的節點者。檢索開始節點之指定 所說明之各種應用檢索中被進行。 接下來，在步驟S4 02中，將所取得之配 在探索經路3 1 0中，在步驟S 4 0 3中，將對應於 之配列要素作爲應參考之節點而讀出。而：j S404中，從所讀出之節點，來取出節點種類 S405中，判定節點種類別是否爲分支節點。 在步驟S405之判定中，當所讀出之節點 點的情況時，前進至步驟S406，並從節點取 位元位置之資訊，進而，在步驟S407中，將 出之辨別位元位置的位元値從檢索鍵中取出。 驟S408中，從節點而取出代表節點號碼，在^ ’將從檢索鍵所取出之位元値與代表節點號碼 到新的配列號碼，而回到步驟S402。 人所提案之 節點樹中之 包含之索引 部分作介紹 請的上述曰 基本動作之 點之配列號 存構成耦合 ，係在於後 列號碼儲存 該配列號碼 麦，在步驟 別，在步驟 係爲分支節 出關於辨別 對應於所取 而後，在步 梦驟 S409中 作加算，得 -20- 200834356 之後，反覆進行從步驟S402起直到步驟S409爲止之 處理，直到在步驟S405之判定中被判定爲葉節點，而前 進至步驟S410爲止。在步驟S410中，從葉節點中取出索 引鍵，並結束處理。

圖5，係爲展示在身爲本申請人所致之申請的上述曰 本特願2006-2 9361 9中所提案之求取出被儲存於耦合節點 樹（包含部分樹）中之索引鍵的最小値之處理的流程圖。從 如先前所述一般之索引鍵的在樹上之配置可以推出，求取 索引鍵之最小値的處理，係相當於從檢索開始節點起而將 節點[〇]在樹上作探索直到到達葉節點爲止。 首先，從步驟S501之檢索開始節點的配列號碼之取 得起，直到步驟S 5 05之節點種類別的判定爲止，係分別 與上述之圖4的步驟S401起直到步驟S405爲止的處理相同 在步驟S 5 05之節點種類別之判定中，若是節點種類 別被判定爲分支節點，則前進至步驟S506，從節點中取 出配列之代表節點號碼，並在步驟S5 07中，在所取出之 代表節點號碼上加算上値“0”，而將該結果作爲新的配列 號碼，並回到步驟S502。之後，在步驟 S805中，反覆進 行步驟S502起到步驟S507爲止之處理，直到該節點被判 定爲葉節點爲止，並在步驟S 508中，從葉節點中來取出 索引鍵，而結束處理。 在上述之圖5所示的處理中，爲了探索節點[0]，係在 代表節點號碼上一律加算上“0，，。亦即是，若藉由圖5之處 -21 - 200834356 理，則連結目標之節點，在節點對之中，係必定爲節點 [〇]，並分歧向被儲存有較小之値的索引鍵之節點。藉由 此，能夠取出樹之構造爲如前所述一般之順列構成的耦合 節點樹之最小的索引鍵。 圖6，係爲展示在身.爲本申請人所致之申請的上述曰 本特願2006-293619中所提案之求取出被儲存於耦合節點 樹（包含部分樹）中之索引鍵的最大値之處理的流程圖。

求取索引鍵之最大値的處理，係相當於針對樹上之節 點中的節點[1 ]，而依序進行探索，直到到達葉節點爲止 的處理。以下，針對求取任意之部分樹的最大之索引鍵的 處理，一面與上述求取最小之索引鍵的處理作比較，一面 以相異點爲中心來作說明。 在圖6所示之一連串的處理中，關於步驟S601起直到 步驟606爲止、以及步驟S608，係分別對應於圖5之步驟 S501起至步驟S 506，以及步驟S 5 08，而被實行同樣的處 理。與圖5之求取最小値的處理相異之點，係在於：在步 驟S607中，於代表節點號碼中，係加算有値“1”之點。藉 由此，在代表節點號碼所表示的節點對之中，係成爲恆常 對節點[1]作連結，藉由反覆依序進行從步驟S602起到步 驟S607爲止的處理直到到達葉節點爲止，能夠得到索引 鍵之最大値。 如同由圖4至圖6所示，在檢索與檢索鍵一致之索引鍵 的基本動作、或是實行索引鍵之最小値/最大値之檢索處 理的情況時，係將所參考之配列的配列號碼依序儲存至探 -22- 200834356 索路徑堆疊310中。

另外’在參考了上述圖5至圖6之索引鍵的最小値/最 大値之檢索處理中，雖係將耦合節點樹作爲被記憶於配列 中者而作了說明’但是，耦合節點樹係並非必須被記憶在 配列中’明顯的’亦可藉由僅對構成節點對之2個的節點 中之代表節點’或者是僅對被配置於與代表節點相鄰接之 記憶區域中的節點作連結，而到達前述葉節點，來求取出 索引鍵之最小値/最大値。 圖7A以及圖7B，係爲展示在身爲本申請人所致之申 請的上述日本特願2006-293619中所提案之求取出被儲存 於耦合節點樹中之索引鍵的下限値之處理的流程圖。於此 ’所謂下限値，係指所指定之下限鍵以上之索引鍵的最小 値。於圖7A以及圖7B中所示之求取下限値的處理，係被 應用於：當針對使用者等所指定之檢索範圍而進行檢索時 ’將實際上索引鍵所無法具有之範圍作爲對象外，並針對 實際上包含有索引鍵之範圍而進行檢索之處理。另外，在 圖7A以及圖7B中，對於所指定之下限鍵以及上限鍵的取 得處理，係被省略。在之後的各種應用檢索中，亦爲相同 首先，在步驟S701中，將檢索開始節點之配列號碼 ，設定爲根節點之配列號碼，並在步驟S702中，進行最 小値檢索處理，而求取出索引鍵之最小値。而，在步驟 S703中，將下限鍵與在步驟S702中所求取之最小値作比 較，並判定下限鍵是否較最小値爲大。當下限鍵具有最小 -23- 200834356 値以下之値時，則前進至步驟S704，將在步驟S702中所 求取出之最小値設定爲下限値，並結束處理。

在步驟S703中，當下限鍵被判定爲較在步驟S7〇2中 所求取之最小値爲更大時，則前進至步驟S705，將下限 鍵設定爲檢索鍵。而，在步驟S 7 06中，將檢索開始節點 之配列號碼，設定爲根節點之配列號碼，並在步驟S 7 0 7 中，藉由以圖4以及圖5所說明之位元列檢索方法，來檢索 出索引鍵。而後，在步驟S708中，將檢索鍵與步驟S707 之檢索結果所得到的索引鍵作比較，並判定値是否爲一致 。當判定檢索鍵與索引鍵係爲相等時，前進至步驟S709 ，將藉由檢索而得到之索引鍵設定爲上述下限値，並結束 處理。當判定檢索鍵與索引鍵係並不相等時，則前進至圖 7B之步驟S710。 在步驟S 7 1 0中，判定檢索鍵與索引鍵之大小關係。 於此，當檢索鍵爲較索引鍵更大的情況時，則該索引鍵係 爲較檢索鍵、亦即是較下限鍵爲更小，而代表其係並不被 包含在藉由使用者等所指定的檢索範圍之內。另一方面， 當檢索鍵爲較索引鍵更小的情況時，則代表該索引鍵係被 包含於所指定的檢索範圍之內。於此，若是判定檢索鍵係 較索引鍵爲更小，則前進至步驟S718，將該索引鍵設定 爲下限値，並結束處理。 在步驟S710中，若是判定檢索鍵係較索引鍵爲更大 ，則前進至步驟S71 1。從步驟S71 1起至步驟S717之處理 ，係爲以昇順而將索引鍵取出之處理，藉由從步驟S7 1 1 -24- 200834356 起直到步驟S7 17爲止的處理，被儲存在耦合節點樹中之 索引鍵係依序被取出，而若是得到具有較檢索鍵、亦即是 較下限鍵爲更大之値的索引鍵，則將該索引鍵設定爲下限 値。

圖8 A以及圖8 B，係爲展示在身爲本申請人所致之申 請的上述日本特願2006-293619中所提案之求取出被儲存 於耦合節點樹中之索引鍵的上限値之處理的流程圖。於此 ，所謂上限値，係指所指定之上限鍵以下之索引鍵的最大 値。於圖8A以及圖8B中所示之求取上限値的處理，係與 上述之求取下限値的處理同樣地，被應用於：當針對使用 者等所指定之檢索範圍而進行檢索時，將實際上索引鍵所 無法具有之範圍作爲對象外，並針對實際上包含有索引鍵 之範圍而進行檢索之處理等。 首先，關於在步驟S801中將根節點作爲檢索開始節 點而進行檢索之處理，係與求取索引鍵之下限値的處理爲 相同，又，關於步驟S 8 02之後的處理，係分別對應於上 述步驟S702之後的處理。 亦即是，在使用圖7A以及圖7B所說明了的求取下限 値之處理中，係藉由步驟S 7 02之後的處理，來檢索出·· 藉由使用者等所指定之下限鍵，和在被包含於耦合節點樹 內的索引鍵之中，具有爲下限鍵以上，且最爲接近下限鍵 之値的索引鍵。相對於此，在圖8A以及圖8B所展示的求 取上限値之處理中，係藉由步驟S802之後的處理，來檢 索出：具備有作爲檢索範圍之上限而藉由使用者等所指定 -25- 200834356 之上限鍵以下之値，且最爲接近上限鍵之値的索引鍵。

若是對圖7A以及圖7B中所示之處理作比較，則在將 所指定之鍵（下限鍵/上限鍵）與索引鍵作比較時之大小關係 (步驟S703與步驟S710、以及步驟S803與步驟S810)之點 ’或是在將所指定之鍵作爲檢索鍵而對耦合節點樹作檢索 時之分別求取出索引鍵的最小値/最大値（步驟S707以及步 驟S 807)之點，以及對索引鍵作求取時之順序分別爲昇順/ 降順（步驟S711以及步驟S811之後的處理）之點上，係爲 相反，但是，直到求取出下限値以及上限値爲止的程序， 基本上係與上述相同。 針對步驟S 802之後的處理，作具體說明。 若是在步驟S802中求取出被包含在耦合節點樹中的 索引鍵之最大値，則在步驟S803中，將在步驟S802中所 求取出之最大値與上限鍵作比較，並判定上限鍵是否爲較 最大値更大。當上限鍵爲索引鍵之最大値以上時，則前進 至步驟S804，將在步驟S802中所求取出之最大値設定爲 上限値，並結束處理。 當上限鍵爲較最大値更小的情況時，前進至步驟 S 805，將上限鍵設定爲檢索鍵。而後，在步驟S806中， 將檢索開始節點之配列號碼，設定爲根節點之配列號碼， 並在步驟S807中，進行關於檢索鍵之檢索處潘，而前進 至步驟S 8 0 8。 在步驟S 8 0 8中，判定檢索鍵與在步驟S 8 0 7中所取得 之索引鍵是否爲相等。當在步驟S 8 0 8中判定此些之値係 -26 - 200834356 爲相等時，前進至步驟S 8 0 9，將藉由步驟s 8 07之處理而 得到之索引鍵設定爲上述上限値，並結束處理。當在步驟 S 8 08中判定係並不相等時，則前進至圖8B之步驟S810。

在步驟S810中，判定檢索鍵與索引鍵之大小關係。 於此，當檢索鍵爲較索引鍵更小的情況時，則代表該索引 鍵係並不被包含於較檢索鍵、亦即是較上限鍵更小之藉由 使用者等所指定的檢索範圍之內。另一方面，當檢索鍵爲 較索引鍵更大的情況時，則代表該索引鍵係被包含於所指 定的檢索範圍之內。於此，若是判定檢索鍵係較索引鍵爲 更大，則前進至步驟S81 8，將該索引鍵設定爲上限値， 並結束處理。 在步驟S810中，若是判定檢索鍵係較索引鍵爲更大 ，則前進至步驟S 8 1 1。在步驟S 8 1 1之後的處理，係爲將 索引鍵以降順來取出的處理，反覆進行從步驟S810起至 步驟S 8 1 7爲止的處理，直到判定檢索鍵爲較索引鍵爲更 大爲止。 接下來，藉由圖9A〜圖9C、圖10，對在身爲本申請 人所致之申請的上述日本特願200 6-187827中所提案之耦 合節點樹中的節點插入處理作說明。圖9 A〜圖9 C，係爲 說明通常之插入處理者，而圖1 0，係爲說明根節點之插入 處理者。由於藉由根節點之插入處理與通常之插入處理， 耦合節點樹係被產生，因此，節點插入說明處理之說明， 係亦爲耦合節點樹之生成處理的說明。 圖9A係爲展示身爲插入處理之前段的檢索處理之處 -27- 200834356 理流程的圖，而相當於在圖4所示之檢索處理中將插入鍵 作爲檢索鍵者。步驟S901係相當於在圖4之步驟S4〇1中將 檢索開始節點作爲根節點者，步驟S902〜步驟S91〇之處 理，由於係完全對應於圖4之步驟S402〜步驟S41〇，故省 略其說明。

在圖9A之步驟S91 1中，將插入鍵與索引鍵作比較， 若是相等，則由於插入鍵係已存在於耦合節點樹中，因此 插入係成爲失敗，而結束處理。而若是不相等，則進行接 下來之處理，亦即是前進至圖9B之步驟S912以下的處理 圖9B ’係爲用以說明爲了對欲插入之節點對所需要的 配列要素作準備之處理的處理流程圖。 在步驟S 9 1 2中，從配列中求取空的節點對，並取得 於該節點對中應成爲代表節點的配列要素之配列號碼。 前進至步驟S913，將插入鍵與在步驟S910中所得到 之索引鍵的大小作比較，當插入鍵爲較大的情況時，得到 値1之布林値，當較小時，則得到値〇的布林値。 前進至步驟S914，在以步驟S912所得到的代表節點 之配列號碼上，加算上以步驟S9 1 3所得到之布林値，而 得到配列號碼。 前進至步驟S915，而得到在以步驟S912所得到的代 表節點之配列號碼上加算上以步驟S9 1 3所得到之布林値 的邏輯否定値後的配列號碼。 在步驟S914所得之配列號碼，係爲儲存有將插入鍵 -28· 200834356 作爲索引鍵而持有之葉節點的配列要素之配列號碼，在步 驟S915所得到之配列號碼，則係爲與該葉節點成對之分 支節點所被儲存之配列要素者。 亦即是，藉由被儲存於在前段之檢索處理中所得到之 葉節點中的索引鍵與插入鍵之大小，來決定在所插入之節 點對中的何者之節點處，儲存保持有插入鍵之葉節點。

例如，當在圖2B之耦合節點樹中插入“011011”的情 況時，檢索結果之索引鍵，係成爲被儲存於節點2 1 1 d中 之“01 1010”。藉由插入鍵“01 1011”與被儲存於節點21 Id中 之索引鍵“0110 10”間的大小比較，求取出布林値，在現在 之例中，由於插入鍵係爲較大，因此係得到布林値1，並 在將所插入之節點對的代表節點號碼上加上1後之配列要 素中，儲存保持有插入鍵之葉節點。另一方面，索引鍵 “0 1 1 0 1 0”，係被儲存於將以大小比較所得到之布林値作邏 輯反轉後所得之値加算至代表節點號碼上後之配列號碼的 配列要素中。 此時，由於索引鍵“011010”與插入鍵“011011”間，係 爲在第5位元成爲相異，因此，節點2 1 1 d，係成爲：將辨 別位元位置設爲5，並將代表節點號碼作爲所插入之節點 對的代表節點之配列號碼的分支節點。 又，當欲在圖2B之耦合節點樹中插入“〇1 1001”的情 況時，檢索結果之索引鍵，係成爲被儲存於節點211d中 之“0 1 1 0 1 0”。於此情況中，由於插入鍵係爲較小，因此得 到布林値0，並在將所插入之節點對的代表節點號碼上加 -29 - 200834356 上了 〇之配列要素中，儲存保持有插入鍵之葉節點。而後 ，由於索引鍵“01 1010”與插入鍵“01 1001”間，係爲在第4 位元成爲相異，因此，節點2 1 1 d，係成爲··將辨別位元位 置設爲4，並將代表節點號碼作爲所插入之節點對的代表 節點之配列號碼的分支節點。接下來，前進至圖9C之步 驟S916以下的處理。

圖9C係爲展示：在將節點儲存於在圖9B所準備之配 列中的同時，求取其插入位置，並改變既存之節點的內容 ，而完成插入處理的處理流程之圖。 從步驟S916〜步驟S923爲止的處理，係爲求取出所 插入之節點對的在耦合節點樹上之位置的處理，而步驟 S 924以下之處理，係爲在各節點中設定資料並完成插入處 理的處理。 在步驟S916中，將插入鍵與在步驟S910中所得到之 索引鍵的位元列，以例如排他之邏輯和來進行比較，並得 到差分位元列。 前進至步驟S917，從在步驟S916中所得到的差分位 元列，而得到從上位之第〇位元起所看到之最初的不一致 位元之位元位置。此處理，例如在具備有優先編碼器 (priority encoder)的CPU中，係於該處輸入差分位元列， 而可得到不一致之位元位置。又，亦可軟體式的進行與優 先編碼器同等之處理，而得到最初之不一致位元的位元位 置。 接下來，前進至步驟S918，並判定探索經路堆疊之 -30- 200834356 堆疊指標是否指向根節點之配列號碼。若是係指向該處， 則移行至步驟S924，若是未指向該處，則前進至步驟 S919 〇 在步驟S 9 1 9中，係將探索經路之堆疊指標倒退一個 ，並取出被堆疊於該處之配列號碼。 前進至步驟S920，將在步驟S919中所取出的配列號 碼之配列要素，從配列中作爲節點而讀取出。

前進至步驟S921，從在步驟S920所讀取出之節點中 ，取出辨別位元位置。 接下來，前進至步驟S922，判定在步驟S921中所取 出之辨別位元位置是否爲較在步驟S917中所得到之位元 位置更上位之位置關係。於此，所謂的上位之位置關係， 係指位元列之靠左側的位置，亦即是位元位置之値爲小的 位置。 若是步驟 S922之判定結果係爲否定，則回到步驟 S918，並反覆進行處理，直到在步驟S918之判定成爲肯 定，或是在步驟S922之判定成爲肯定爲止。若是在步驟 S922之判定成爲肯定，則在步驟S923中，使探索路徑堆 疊之指標前進1個，並移行至步驟S9 24以下之處理。 在上述步驟S916〜步驟S923中所說明之處理，係爲 了決定插入之節點對的插入位置’而對所插入之索引鍵與 藉由檢索所取得之索引鍵之間，進行位元列比較，並對在 位元列比較中成爲相異之位元値的前端之（最上位之）位元 位置與被儲存於堆疊中之分支節點的辨別位元位置之相對 -31 - 200834356 的位置關係作調查，而將辨別位元位置成爲上位之分支節 點的下一個分支節點之連結目標，作爲所插入之節點對的 插入位置。

例如，當在圖2B之耦合節點樹中插入“1 1 1 000”的情 況時，檢索結果之索引鍵，係成爲被儲存於節點2 1 Oh中 之“10101 1”。藉由對插入鍵“ 1 1 1 000”與被儲存於節點21 Oh 中之索引鍵“ 1 0 1 0 1 1”所進行的位元列比較，而得到成爲相 異位元値之最上位的位元位置1。若是對所得到之位元位 置1與被儲存在堆積於經路探索堆疊中之配列號碼的配列 要素中之分支節點的辨別位元位置間之位置關係，以使辨 別位元位置成爲上位爲止的方式，來以反方向而依序對探 索路徑堆疊作探索，則會到達根節點2 1 0a。於此，使探索 路徑堆疊之指標前進1個，而得到節點2 1 1 b之配列號碼。 插入鍵“1 1 1 000”係被插入至節點2 lib之連結目標處。 又，若是就算是以反方向來對探索經路堆疊作探索並 到達根節點，該根節點之辨別位元位置，亦係並非爲較在 先前所求取之位元列比較中成爲相異位元値之最上位的位 元位置更上位之位元位置，則係表示：在該耦合節點樹之 索引鍵的上位位元中，較根節點之辨別位元位置爲更上位 的上位之位元的値係全部爲相等。而，在所插入之索引鍵 中，第一次出現有在較根節點之辨別位元位置更上位的位 元之値中具有相異之位元値者。故而，所插入之節點對， 係成爲根節點之直接的連結目標，根節點之辨別位元位置 ，係變更爲身爲與既存之索引鍵爲相異値之插入鍵的最上 -32- 200834356 位位元之位置。 接下來’針對步驟S924以下之在各節點中設定資料 並完成插入處理的處理作說明。 在步驟S924中，係從探索經路堆疊中將指標所指向 之配列號碼取出。

在步驟S925中，在以步驟S9 14所得到之配列號碼所 指向的配列要素之節點種類別中寫入i (葉節點），並在索 引鍵中寫入插入鍵。 前進至步驟S926，將在步驟S924中所取出的配列號 碼之配列要素，從配列中讀取出。 接下來’在步驟S927中，在以步驟S915所得到之配 列號碼的配列要素中，將藉由步驟S 9 2 6所讀出的內容寫 入。 最後’在步驟S92 8中，在以步驟 S924所得到之配列 號碼所指向的配列要素之節點種類別中寫入〇 (分支節點） ’並在辨別位元位置中寫入以步驟S9〗7所得到之位元位 置’在代表節點號碼中寫入以步驟S91 2所得到之配列號 碼，而結束處理。 在上述之於圖2 B的耦合節點樹中插入“ 1 1 1 〇 〇 〇，，的例 中’係在所取得之空節點對的節點[0]中，寫入節點21 lb 之內容（步驟S927)，並將節點[1]，作爲保持插入鍵 “1 1 1000”之葉節點（步驟S925)。而後，在節點211b之辨 別位元位置中’儲存藉由位元列比較而成爲相異之位元値 的最上位之位元位置1，而在代表節點號碼中，係儲存有 -33- 200834356 所取得之節點對的代表節點所被儲存之配列要素的配列號 碼（步驟S928)。 圖10，係爲對在身爲本申請人所致之申請的上述曰本 特願2006-187827中所提案之將包含有根節點之插入處理 的索引鍵作追加時之節點插入處理全體作說明的處理流程 圖。

在步驟S 1 0 1中，判定被要求作取得之耦合節點樹的 根節點之配列號碼是否爲已完成登錄。若係爲已完成登錄 ，則係進行使用圖9A〜圖9C而說明了的通常之插入處理 在步驟S 1 0 1中之判定，若是係爲未完成登錄，則係 成爲開始全新之耦合節點樹的登錄、產生。 首先，在步驟S1 02中，從配列中求取空的節點對， 並取得於該節點對中應成爲代表節點的配列要素之配列號 碼。接下來，在步驟S103中，求取出在以步驟S102所得 到之配列號碼中加上〇的配列號碼（實際上，係相等於在步 驟S102中所取得之配列號碼）。進而，在步驟S104中，在 以步驟S 1 03所得到之配列號碼的配列要素中，於插入之 根節點的節點種類別中寫入1 (葉節點），並於索引鍵中寫 入插入鍵，而在步驟S105中，將以步驟S102所取得之根 節點的配列號碼作登錄，並結束處理。 如先前亦所述一般，明顯的，當存在有索引鍵之集合 時，藉由從該處依序取出索引鍵，並反覆進行圖1 0以及圖 9A〜圖9C之處理，而能夠建構對應於索引鍵之集合的本 -34- 200834356 發明之耦合節點樹。 接下來’參考圖11A、圖11B，對於在身爲本申請人 所致之申請的上述日本特願2006-1 87 827中所提案之從耦 合節點樹中之索引鍵的集合，來將特定之索引鍵作削除的 處理流程作說明。

圖1 1 A，係爲展示身爲削除處理之前段的檢索處理之 處理流程的圖，而相當於在圖4所示之檢索處理中將削除 鍵作爲檢索鍵者。步驟S1 101係相當於在圖4之步驟S4 01 中將檢索開始節點作爲根節點者，步驟 S 1 1 02〜步驟 SI 1 10之處理，由於係完全對應於圖4之步驟S402〜步驟 S410，故省略其說明。 在圖11A之步驟S1111中，將削除鍵與索引鍵作比較 ，若是不相等，則由於欲削除之索引鍵鍵係不存在於耦合 節點樹中，因此削除係成爲失敗，而結束處理。而若是相 等，則進行接下來的處理，亦即是前進至圖1 1 B之步驟 SI 1 12以下的處理。 圖1 1 B，係爲說明削除處理之後段的處理流程之圖。 首先，在步驟S 1 1 1 2中，判定在探索經路堆疊中是否 被儲存有2個以上的配列號碼。若是未被儲存有2個以上的 配列號碼，換句話說，僅存在有1個，則該配列號碼係爲 被儲存有根節點之配列要素。於該情況，係移行至步驟 S 1 1 1 8，並將屬於以步驟S 1 1 0 1所得到之根節點的配列號 碼之節點對削除。接下來，前進至步驟S 1 1 1 9，並將被登 錄之根節點的配列號碼削除，而結束處理。 -35- 200834356 在步驟S1112中，若是被判定爲在探索經路堆疊中係 儲存有2個以上的配列號碼，則前進至步驟S 1 1 1 3，並得 到在以步驟S 1 1 08所得到之代表節點號碼中加算有將以步 驟S 1 1 07所得到之位元値反轉後的値後之配列號碼。此處 理，係爲求取與身爲削除對象之索引鍵所被儲存之葉節點 成對之節點的所被配置之配列號碼者。

接下來，在步驟S 1 1 1 4中，讀取出以步驟S 1 1 1 3所得 到之配列號碼的配列要素之內容，並在步驟S1115中，將 探索路徑堆疊之堆疊指標倒退1個，而取出配列號碼。 接下來，前進至步驟S 1 1 1 6，將在以步驟S 1 1 1 4所讀 出之配列要素的內容，抹寫至以步驟S 1 11 5所得到的配列 號碼之配列要素中。此處理，係爲將身爲對削除對象之索 引鍵所被儲存之葉節點之連結源頭的分支節點，置換爲與 上述葉節點成對之節點者。 最後，在步驟s 1 1 1 7中，將相關於以步驟s 1 1 0 8所得 到之代表節點號碼的節點對作削除，並結束處理。 以上’雖係通於成爲關於f禹合卽點樹之分割/結合的 本發明之前提的技術作了說明，但是，若是有必要，則請 參考上述之專利申請的說明書以及圖面的記載。 接下來，針對本發明之耦合節點樹之分割/結合方法 作說明。 於此，所謂的耦合節點樹之分割，係指當指定有由某 位元列所成之分割鍵時，將被包含於耦合節點樹中之索引 鍵，藉由與該分割鍵間之大小關係而分成2個群組，並產 -36- 200834356 生由屬於分別之群組的索引鍵所成之2個的耦合節點樹一 事。 關於以大小關係所致之分割，在以下之說明中，係設 爲將其分割成較分割鍵爲更大之群組與爲分割鍵以下之群 組’但是，由以下之說明中，應可容易的理解，在將其分 割成分割鍵以上之群組與較分割鍵爲更小之群組的情況時 ，亦同樣的可進行分割/結合。

也就是說，分割鍵，係爲用以決定將耦合節點樹在何 處作分割的鍵。 又，所謂耦合節點樹之結合，係指從對應於2個的索 引鍵之集合的2個耦合節點樹，來產生對應於2個的索引鍵 之集合的和集合之耦合節點樹一事。在本發明中，係以2 個的索引鍵之集合的積集合係爲空的一事作爲前提。 以下，雖係針對本發明之3個的實施例作說明，但是 ’在此說明中，亦有將耦合節點樹單純稱爲樹的情況。在 以下所說明之實施例1、2以及3中，在分割處理對象之樹 中，雖然並不一定需要包含有與所指定之分割鍵相等的索 引鍵，但是，當將對應於所指定之分割鍵的索引鍵作爲分 割鍵時，係可將所指定之分割鍵作爲上限鍵或是下限鍵， 並藉由參考圖7A、圖7B、圖8B所說明了的檢索方法，而 求取出上限値或是下限値，並將其設定爲對應於所指定的 分割鍵之新的分割鍵。 [實施例1] -37· 200834356

本實施例1，係取出身爲分割對象之處理源頭的樹（以 下，亦有單純稱爲處理源頭的情況）之索引鍵的最小値， 並將所取出之索引鍵的最小値，插入至藉由處理源頭之分 割所產生的處理目標之樹（以下，亦有單純稱爲處理目標 的情況）中，而從處理源頭之樹來將索引鍵之最小値削除 ，並藉由反覆進行上述之處理，直到最小値係成爲分割鍵 以下，而從身爲分割對象之處理源頭的樹中來分割出處理 目標之樹。 圖1 2，係爲說明本發明之實施例1中的耦合節點樹之 分割處理流程的圖。 將在最初之步驟S 1 20 1中所指定的分割鍵，設定爲處 理源頭之分割鍵。分割鍵之指定，係可能爲操作者所致之 外部輸入的情況，亦可能爲某一電腦程式之處理結果所致 的情況，亦可能爲由從遠處而來之指令所致的情況等。所 指定之分割鍵，係被設定於將處理源頭之分割鍵作保持之 記憶體上的區域中。 接下來，在步驟S 1 202中，將處理源頭之根節點，設 定爲處理源頭之檢索開始節點，並前進至步驟S 1 203。 在步驟S 1 203中，係判定處理源頭之樹爲已完成登錄 。由於當此判定結果爲尙未完成登錄的情況時，係表示處 理源頭之樹爲全部完成削除，因此，係爲分割鍵爲處理源 頭之樹的索引鍵之最大値以上的例外情況，當此情況時， 處理係結束。 若是處理源頭之樹係爲已完成登錄，則移動至步驟 -38- 200834356 S 1204，藉由在步驟S 1 202中作爲檢索開始節點而設定的 根節點，來實行於圖5中所示之處理，而得到索引鍵之最 小値。

接下來，前進至步驟S 1 205，判定在步驟S 1204中所 得到之最小値是否較分割鍵爲更大。若是最小値係較分割 鍵爲更大，則表示樹之分割係爲完成，因此，處理係結束 ，而若是並未較分割鍵爲大，則實行在以下所說明之步驟 S 1206〜步驟S 1 209的處理目標之樹的產生與從處理源頭 之樹的節點之削除處理，而回到步驟S 1 203。 在步驟S 1 206中，係將在步驟S 1 204中所得到之最小 値，設定爲處理目標之插入鍵。 接下來，在步驟S 1 207中，藉由圖9A〜圖9C、圖10中 所示之樹的產生、插入處理，而實行插入鍵所致的處理目 標之樹的產生。 接下來，在步驟S 1 208中，將在步驟S 1 207中之插入 鍵設定爲處理源頭之削除鍵，並在步驟S 1209中，藉由於 圖1 1 A、圖1 1 B中所示之削除處理，來從處理源頭之樹中 將包含有削除鍵之葉節點削除。 在上述分割處理之說明中，雖係設爲從處理源頭之索 引鍵的最小値起而依序作削除，但是，只要是同業者，則 應可輕易明瞭，亦可同樣地從索引鍵之最大値起而依序進 行削除。於該情況，步驟S 1204係成爲求取索引鍵之最大 値的處理，步驟S 1 205係成爲最大値與分割鍵間之大小關 係的判定處理，而在步驟S 1 206中，係成爲將最大値設定 -39- 200834356 爲處理目標之插入鍵。 以上，雖係針對分割處理作了說明，但是，結合處理 亦可藉由於圖1 2中所示之處理流程來實行。

結合處理，若是將欲結合之2個的樹之中的其中一者 作爲處理源頭之樹，並將分割鍵設爲處理源頭之樹的索引 鍵之最大値以上，則係相當於先前所述之例外的處理，處 理源頭之樹係被削除，而被結合至處理目標之樹中。另外 ，當處理源頭之樹的索引鍵之最大値係爲未知的情況時， 則係成爲事先藉由於圖6中所示之最大値檢索處理，來求 取出分割鍵。 而後，由於係將處理源頭之分割鍵設爲處理源頭之樹 的索引鍵之最大値以上，因此，在步驟S 1 205之大小比較 中，分割鍵係恆常較最小値爲大而分歧至步驟S 1206，故 而，係可省略步驟S 1 205。若是如此，則設定分割鍵一事 亦成爲無意義，因此，最終，步驟S1 201係亦成爲不必要 ，而可僅單純地藉由最小値檢索與插入處理與削除處理的 反覆進行，來進行結合處理。 又，如同在分割處理中所述一般，明顯的，亦可藉由 最大値檢索與插入處理與削除處理之反覆進行，而進行結 合處理。 本實施例1，其處理之邏輯雖係爲簡單，但是’由於 係反覆進行將處理源頭之根節點作爲檢索開始節點的最小 値檢索，並以索引鍵單位來進行插入削除處理，因此，實 行時之處理步驟數係變大。 -40- 200834356 [實施例2] 本實施例2，在以索引鍵單位來進行插入削除之點上 ，雖係與實施例1相同，但是，係爲藉由在應插入削除之 索引鍵的檢索中活用探索路徑堆疊，而將插入處理以及削 除處理的實行時之處理步驟數減少者。

圖1 3，係爲說明本發明之實施例2中的耦合節點樹之 分割處理流程的圖。 從步驟S1301起至步驟S 1 306爲止之處理，由於係爲 和圖12所示之實施例1的步驟S1201起至步驟S 1 206爲止的 處理完全相同，故省略其說明。 在步驟S 1 3 07中，藉由插入鍵，而在處理目標中插入 節點。此處理，係和在圖1 2中所示之步驟S 1 207的插入處 理相異，而爲在本實施例中之特有者，於後，係參考圖i 4 、圖1 5 A、圖1 5B而作詳細說明。 接下來，在步驟S1308中，將包含有在步驟S 1 304中 所得到之最小値的節點，作爲處理源頭之削除節點而設定 ，在步驟S1309中，從處理源頭而將削除節點削除，而得 到將與削除節點成對之節點的內容複製的處理源頭之母節 接下來，在步驟S1310中，將在步驟Si 309中所得到 之處理源頭之母節點，設定爲處理源頭之檢索開始節點， 並回到步驟S 1 3 0 3。 如同後述所說明一般，處理源頭之削除節點，係爲削 •41 200834356 除節點之近旁的上位之分支節點。削除節點，係爲包含有 處理源頭之索引鍵的最小値者，從先前所述之索引鍵的順 序性可知，下一個所檢索之最小値，係在處理源頭之母節 點的下位。 故而，藉由並不將於第2次之後的步驟S13〇4中之最 小値檢索的檢索開始節點作爲根節點，而作爲處理源頭之 母節點，可以減低處理步驟數。

關於步驟S1308〜步驟S1309、以及處理源頭之母節 點，於後，參考圖16並作詳細說明。 圖1 4，係爲說明對應於圖1 3所示的步驟S 1 3 0 6與步驟 S 1 3 07之節點的插入處理流程之圖。 在最初之步驟S 1 40 1中的將插入鍵作爲處理目標之插 入鍵而設定的步驟，係爲對應於圖1 3所示之步驟S 1 3 0 6的 處理，而將在圖13所示之步驟S 1 304中所得到的最小値， 設定於處理目標之插入鍵設定區域中。 接下來，在步驟S1402中，判定處理目標是否爲已完 成登錄。 若是並非爲已完成登錄，則係移動至步驟S 1 403，在 步驟S 1 403中，將包含有插入鍵之節點對設定於處理目標 之根節點中，並作爲處理目標之根節點而登錄。接下來， 前進至步驟S 1404，並將處理目標之根節點作爲插入完成 之節點而設定，而結束處理。 在上述步驟S1 4 0 2中之判定結果若是爲已完成登錄， 則係移動至步驟S1405。在步驟S1405中，係判定插入完 -42- 200834356 成之節點是否爲已完成設定。此判定處理，係爲於後所說 明之樹的結合處理中成爲必要者。在樹之分割處理中，於 最初之插入處理中，由於在步驟S1404中係將根節點作爲 插入完成之節點而設定，因此，在步驟S1 406中之判定， 係恆常成爲「是」。故而，若是僅爲了進行分割處理，則 步驟S 1405與步驟S 1 407係並非爲必要。

右疋在步驟S 1 4 0 5中之判疋結果係爲「是」’則目丨j進 至步驟S 1 406，並將作爲插入完成之節點而設定之節點設 定爲處理目標之檢索開始節點，而前進至步驟S 1 408。 若是在步驟S 1405中之判定結果係爲「否」，則前進 至步驟S 1 407，並將根節點設定爲處理目標之檢索開始節 點，而前進至步驟S 1 408。 在步驟S1408中，係藉由圖6所示之最大値檢索處理 ，而從在步驟S 1406或者是步驟S 1407中所設定之檢索開 始節點來求取處理目標之索引鍵的最大値。 接下來，在步驟S 1409中，藉由在步驟S1401中所設 定之插入鍵與在步驟S 1 407中所得到之最大値，來求取出 所插入之節點對的處理目標之母節點，並在該母節點處將 包含有前述插入鍵之節點對插入。 接下來，前進至步驟S1410，將在步驟S 140 9中被插 入有包含插入鍵之節點對的處理目標之母節點，作爲插入 完成之節點而設定，並結束處理。 接下來，針對上述之步驟S1403與步驟S 1409作詳細 說明。 -43- 200834356 圖15A，係爲說明在圖14中所示之步驟S 1 403的根節 點設定處理之流程圖。 首先，在步驟S 1 5 0 1中，從配列中而取得節點對爲空 之代表節點號碼。 接下來，在步驟S 1 502中，將在步驟S1501中所取出 之代表節點號碼上加算上値所得到的配列號碼，作爲 插入節點之配列號碼而設定。

前進至步驟S 1 5 03，爲了形成葉節點，而將節點種類 別設定爲葉，將索引鍵設定爲插入鍵，並儲存於以步驟 S 1 502所設定之配列號碼的配列要素中。 接下來，在步驟S 1 5 04中，將插入節點之配列號碼作 爲根節點之配列號碼而登錄，並結束處理。 另外，上述步驟S1501〜步驟S 1 504之處理，係爲對 應於在參考圖1 〇所說明之耦合節點樹的產生處理中，當根 節點之配列號碼係並非爲已完成登錄的情況時之步驟 S102〜步驟S105者。 圖15B，係爲說明圖14所示之步驟S1409的求取出所 插入之節點對的處理目標之母節點，並在該母節點中插入 包含有前述插入鍵之節點對的處理之流程圖。於圖1 5B中 所示之流程，係爲在身爲本申請人所致之先前的申請之曰 本特願2006- 1 8 7827中所提案之插入處理的應用，在步驟 S 1 5 0 5中之將插入鍵與最大値作爲位元列而比較，並求取 出從上位第〇位元起所發現之最初的不一致位元之位置， 而將其設定於儲存差分位元位置之區域中的處理，係對應 -44- 200834356 於圖9C所示之步驟S916與步驟S917之處理。 接著步驟S 1 505之後，而前進至步驟S 1 506。另外， 步驟S1506〜步驟S1512之處理，係相當於圖9C所示之步 驟S918〜步驟 S923，步驟S1513〜步驟 S1518之處理， 係相當於圖9C所示之步驟S924〜步驟S928。 在步驟S 1 506中，係將處理目標之探索經路的堆疊指 標倒退一個，並取出配列號碼。

接下來，在步驟Sl5〇7中，從配列中而將配列號碼所 指向的配列要素之內容作爲節點而取出。 接下來，在步驟S1508中，從在步驟S1507所讀取出 之節點中，取出辨別位元位置。 接下來，在步驟S 1 509中，對在步驟S 1 5 05中所設定 之差分位元位置與在步驟S1508中所取出之差分位元位置 作比較，並判定辨別位元位置是否較差分位元位置更上位 之位置關係。 其判定之結果’若是辨別位元位置係爲較差分位元位 置更爲上位之位置關係，則前進至步驟S 1 5 1 2，將處理目 標之探索路徑堆疊的堆疊指標前進1個，並取出配列號碼 ，而將其設定於母節點之配列號碼區域中，並移動至步驟 S1513 ° 在步驟S 1 5 0 9中之判定的結果，若是辨別位元位置並 非爲較差分位元位置爲更上位之位置關係，則前進至步驟 S 1 5 1 0 〇 在步驟S 1 5 1 0中，判定處理目標之探索經路堆疊的堆 •45- 200834356 疊指標是否指向根節點之配列號碼。 判定之結果，當處理目標之探索經路堆疊的堆疊指標 並非指向根節點之配列號碼的情況時，則回到步驟S 1 5 0 6

判定之結果，當處理目標之探索經路堆疊的堆疊指標 係指向根節點之配列號碼的情況時，則在步驟S 1 5 1 1中， 從處理目標之探索路徑堆疊中取出堆疊指標所指向之配列 號碼，並設定於儲存處理目標之母節點的配列號碼之區域 中，而移動至步驟S 1 5 1 3。 在步驟S 1 5 1 3中，從配列中而取得節點對爲空之代表 節點號碼。 接下來，在步驟S 1 5 1 4中，將在代表節點號碼上加算 上1所得到的配列號碼，作爲儲存插入節點之配列號碼的 區域而設定。 接下來，在步驟s 1 5 1 5中，爲了形成葉節點，而將節 點種類別設定爲葉，將索引鍵設定爲插入鍵，並儲存於以 步驟S 1 5 1 4所設定之配列號碼的配列要素中。 接下來，在步驟S 1 5 1 6中，將在代表節點號碼上加算 上〇所得到的配列號碼，作爲儲存與插入節點成對之對節 點的配列號碼之區域而設定。 接下來，在步驟S1517中，將在步驟ι51ι或者是步驟 S 1 5 1 2中所設定之處理目標的母節點之配列號碼所指向之 配列要素的內容讀出，並儲存在以步驟S 1 5 1 6所設定之對 節點的配列號碼所指向之配列要素中。 -46- 200834356 接下來，在步驟s 1 5 1 8中，爲了形成分支節點，而在 節點種類別中設定分支，在辨別位元位置中設定以步驟 S 1 5 05所設定之差分位元位置，在代表節點號碼中設定以 步驟S 1 5 1 6所設定之對節點的配列號碼，並儲存在以步驟 S 1 5 1 1或者是步驟S 1 5 1 2所設定之處理目標的配列號碼所 指向之配列要素中，而結束處理。

圖1 6，係爲展示針對圖1 3所示的處理流程中之削除處 理而說明之處理流程例的圖。 身爲最初之步驟的步驟S 1 60 1，係爲相當於圖1 3所示 之步驟S 1 3 08者。被包含於削除節點中之削除鍵，由於係 爲藉由在圖1 3所示之步驟S 1 3 04中的最小値檢索所求取出 者，因此，由於在處理源頭之探索路徑堆疊中係被堆疊有 儲存削除鍵之配列要素的配列號碼，故讀取出該配列號碼 ，並設定於儲存削除節點之區域中。 接下來，在步驟S 1 602中，判定在處理源頭之探索經 路堆疊中，是否被儲存有2個以上的配列號碼。從此步驟 S 1 602之後直到步驟S 1 60 8的處理，係爲相當於圖11B所 示之在身爲本申請人所致的先前之申請的日本特願2006-1 87827中所提案之削除處理的後段之處理者。 若是在處理源頭之探索路徑堆疊中並未被儲存有2個 以上的配列號碼，則移動至步驟S 1 607，將在步驟S1 601 中所設定之削除節點的配列號碼所指向之節點對削除，並 前進至步驟S 1 608，將根節點之配列號碼削除（抹除其登 錄），而結束處理。 -47- 200834356 若是在處理源頭之探索路徑堆疊中係儲存有2個以上 的配列號碼，則前進至步驟S 1 603，求取出與在步驟 S 1 60 1中所設定之削除節點成對之節點的配列號碼，並設 定於儲存對節點之配列號碼的區域中。

接下來，在步驟S 1 604中，將處理源頭之探索路徑堆 疊的堆疊指標倒退1個，並取出配列號碼，而設定於身爲 削除節點之近旁上位的分支節點之處理源頭的母節點之配 列號碼儲存區域中。 接下來，在步驟S 1 605中，將在步驟1 603中所設定之 對節點的配列號碼所指向之配列要素的內容讀出，並儲存 在以步驟S 1 604所設定之處理源頭的母節點之配列號碼所 指向的配列要素中。 接下來，在步驟S 1 606中，將削除節點之配列號碼所 指向之節點對削除，並結束處理。 以上，雖係針對實施例2之樹分離處理而作了說明， 但是，在實施例2中，亦和實施例1同樣的，可以從索引鍵 之最大値起依序進行削除。 又’與實施例1的情況相同，可將分割處理之處理流 程使用在樹之結合處理中。只要將欲結合之2個的樹中之 任一者作爲處理源頭之樹，並將分割鍵設定爲處理源頭之 樹的索引鍵之最大値以上或者是最小値以下，而進行處理 源頭之樹的削除處理，並進行將所削除之節點插入至處理 目標之樹中的處理即可。 -48- 200834356 [實施例3] 上述之實施例1與實施例2的分割結合方法，雖係爲以 索引鍵單位來進行插入削除者，但是，作爲接下來之實施 例3，係對注目於耦合節點樹之順序性，而將耦合節點樹 之更大的滿足特定條件之部分樹作爲單位，來進行插入削 除的分割結合方法作說明。

圖17，係爲說明在實施例3中之耦合節點樹的分割處 理流程之圖。又，圖30A〜圖30C，係爲將上述處理藉由 實例來作說明之圖，並例示有與在圖2B中所例示之耦合 節點樹相類似之樹。圖3 0 A係爲展示分割前之樹構造例， 圖3 0B係爲展示最初之分割後的樹構造例，圖30C係爲展 示在下一次分割後之樹的構造例。 首先，如圖17所示一般，藉由步驟S001，而取得分 割鍵，並設定於儲存分割鍵之區域中。在圖3 0 A之例示中 ，分割鍵係相等於節點21 lg之索引鍵25 lg的“1 0001 1”。 另外，如同先前所述一般，所取得之分割鍵，雖並不需要 被包含在處理源頭中，但是，如同後面所說明一般，在本 實施例中，係有必要藉由所取得之分割鍵而求取出上限値 或是下限値，並將被包含在處理源頭中之索引鍵作爲新的 分割鍵。故而，在以下之說明中，分割鍵係作爲被包含在 處理源頭中者而作說明。 接下來，在步驟S002中，藉由分割鍵而求取出處理 源頭之分割節點。分割節點，係爲將分割鍵作爲最大値而 包含之部分樹之中的最大者（以下，稱爲分割節點樹。）之 -49- 200834356 根節點。在圖3 0 A之例示中，節點2 1 Of係爲分割節點’以 點線所包圍之部分樹，係爲分割節點樹29 1 °求取分割節 點之處理的詳細，係於後參考圖1 8與圖1 9而作說明。

接下來，前進至步驟S0 03中，判定處理目標是否爲 已完成登錄。若是並非爲已完成登錄，則前進至步驟 S004，將以步驟S002所求取之分割節點，設定爲處理目 標之根節點，並作爲處理目標之根節點而登錄，進而’移 動至步驟S007，並實行分割節點樹之削除處理。另外， 步驟S004之處理的詳細說明，係於後參考圖20而進行。 在圖3 0 A之例示中，分割處理係爲剛開始，如圖3 0 A 之（b)所示一般，由於處理目標係並不存在且並未被登錄 ，因此，前進至步驟S004，將分割節點21 Of之內容作爲 處理目標，而儲存在新取得之節點對20 li的代表節點21 0i 中’並設定爲處理目標之根節點，而作爲處理目標之根節 點並登錄。作爲其結果，如圖30B之（b)所示一般，由被 插入之分割節點樹291所成的處理目標之樹係被產生。 另一方面，在圖30B之（a)中，係展示有從處理源頭而 將以節點21 lg作爲分割節點的分割節點樹291削除後之樹 構造’將分割節點2 1 0b作爲根節點之下一個分割節點樹 2 92 ’係以點線而包圍並展示之。 在步驟S003中之判定結果若是爲已完成登錄，則係 移動至步驟S005。在步驟S005中，係求取出身爲在後述 之步驟S0 1 〇中所設定的下一個分割節點樹之最大値的分 割鍵’與處理目標之最小値，其兩者間的差分位元位置。 -50- 200834356 求取差分位元位置之處理的詳細，係於後參考圖2 1而作說 明。 在圖30B之例示中，下一個分割節點樹292之最大値 ，係爲索引鍵251 c“01 1010”，處理目標之最小値係爲索引 鍵25 0g“ 1 000 1 0”，因此，差分位元位置係爲“〇”。

接下來，前進至步驟S006中，將處理目標之根節點 ，作爲插入位置，並在處理目標中，插入分割節點樹，並 前進至步驟S007。 在步驟S007中，係從處理源頭而將分割節點樹削除 。而後，前進至步驟S008，求取出下一個分割節點。 在圖30C之（1>)中，係展示有：將根節點210丨作爲插 入位置，並經由新取得之節點對20 lj，而將下一個分割節 點樹292插入至處理目標後之樹構造。又，在圖30C之（a) 中，係展示有：從在圖30B之（a)中所展示的樹構造中，將 下一個分割節點樹292削除後之構造。 在步驟006中之分割節點的插入處理、在步驟S007中 之削除處理、以及在步驟S008中之求取下一個分割節點 之處理，其詳細內容，係分別於後參考圖22、圖23、圖24 來作說明。 接著步驟S008之後，在步驟 S009中，判定在步驟 S008中是否求取出了分割節點。若是未求取出分割節點， 則分割處理係成爲結束。 若是求取出有分割節點，則在步驟S 0 1 〇中，求取出 身爲將該分割節點作爲根節點之部分樹的分割節點樹之最 -51 - 200834356 大値，並作爲下一個分割節點，而後，回到步驟S〇05中 ，並反覆進行下一個的分割節點之插入、削除處理，以及 求取出再更下一個之分割節點的處理。 在步驟S 0 1 0中之求取分割節點之最大値，並作爲下 一個分割節點之處理的詳細內容，係於後參考圖25而作說 明。

在本實施例中，由於係如上述所示一般，以分割節點 樹單位來進行削除插入處理，因此，步驟數係被削減。 接下來，參考圖18與圖19，對於圖17中所示之步驟 S0 02中的求取出分割節點之處理作詳細說明。 圖1 8，係爲說明在求取最初之分割節點的處理流程之 前段的圖。 如圖18所示一般，在步驟S1801中，將分割鍵作爲檢 索鍵而設定，並在步驟S 1 802中，將儲存有處理源頭之根 節點的配列要素之配列號碼，作爲檢索開始節點之配列號 碼而設定。 接下來，前進至步驟S 1 803，實行於圖4中所示之檢 索處理，並作爲檢索結果，而得到與分割鍵相等之索引鍵 ，而結束前段之處理，並前進至於圖19中所示之後段的處 理。 後段之處理，雖係參考圖1 9而作說明，但是，於此之 前，再度參考圖3 0 A，而針對在本實施例中將分割鍵作爲 被包含於處理源頭中之索引鍵的必要性作說明。 現在，假設將在圖3 0 A中所展示之處理源頭，以分割 -52- 200834356 鍵“ 1 0 0 0 0 1 ”來進行分割。若是藉由此分割鍵，而實行於圖 18中所示之步驟S1 803的檢索處理，則作爲檢索結果所得 到之索引鍵，係爲索引鍵251g之“1 0001 1 ”。然而’應作 爲分割點之索引鍵，係爲被儲存在葉節點211c中之以 “1 0000 1 ”作爲上限的上限値“011010” ’或是被儲存在葉節 點21 lg中之以“1 0000 1 ”爲下限的下限値“1 000 1 0”，而不論 在何者之情況中，均不會與以分割鍵“1 00001”作檢索後的

結果一致。 故而，在求取分割節點前，有必要先將分割鍵因應於 其定義而作爲被包含在處理源頭中之索引鍵並求取出。 圖1 9，係爲說明在求取最初之分割節點的處理流程之 後段的圖。後段之處理，係探索處理源頭之探索路徑堆疊 ，並求取出最初之節點[〇]，而作爲分割節點之配列號碼 並設定者。 如圖1 9所示一般，在步驟S 1 9 0 1中，判定探索經路堆 疊之堆疊指標是否指向根節點之配列號碼。若是探索路徑 堆疊之堆疊指標係指向根節點的配列號碼，則前進至步驟 S 1 906，並將根節點之配列號碼，設定爲分割節點之配列 號碼，而結束處理。 若是探索路徑堆疊之堆疊指標係並非指向根節點的配 列號碼，則前進至步驟S 1 902，並從探索路徑堆疊中取出 配列號碼，而將堆疊指標減去1個。 接下來，在步驟S 1 903中，從以步驟S 1 902所取出之 配列號碼中，得出被配置在此配列號碼之配列要素中的節 -53- 200834356 點，係位於該當節點對之何側的位置。 而後，在步驟S 1 904中，判定在步驟S 1 903中所得到 之節點位置是否爲節點[1]側。 判定之結果，若是爲節點[1]側，則回到步驟S1 901之 處理，若是爲節點[〇]側，則移動至步驟S190S，將在步驟 S 1 902中所取出之配列號碼，作爲分割節點之配列號碼而 設定，並結束處理。

在圖3 0 A所示之例中，若是將根節點2 1 0a之配列號碼 220，設定爲檢索開始鍵，並藉由分割鍵“ 1 000 1 1 ”而實行 檢索處理，則會得到作爲檢索結果之索引鍵25 1 g，在探索 路徑堆疊中，係依序被堆疊有配列號碼220、22〇a + 1、 221b 、 220f+ 卜 故而，在圖19中所示之步驟SI 901之最初的處理中， 探索路徑堆疊之堆疊指標係指向配列號碼220f+ 1，接下 來，依據步驟 S 1 9 0 4之判定處理的結果，而回到步驟 S 1 9 0 1，在接下來之步驟S 1 9 0 4中，係探索1個，而判定出 配列號碼221b之節點21 Of的節點位置，並移動至步驟 S 1 905，將節點21 Of之配列號碼221b，作爲分割節點之配 列號碼而設定之。 於此，在針對分割處理作更進一步的說明前’先針對 :分割鍵係爲分割節點樹之最大値一事；和分割節點樹係 爲將分割鍵作爲最大値之處理源頭的部分樹中之最大的部 分樹，若以其他方法表現，則係爲該根節點之辨別位元位 置係爲最上位的部分樹一事，進行說明。 -54- 200834356 如同藉由到目前爲止之說明而可明知，分割節點，係 爲在以分割鍵來進行檢索時，直到到達分割鍵爲止之路徑 中所探索的最初之節點[〇]。

將分割鍵作爲索引鍵而包含的葉節點，若是爲節點 [〇]，則該葉節點即爲分割節點本身，而分割節點樹係僅 由1個的葉節點所構成。存在於與此葉節點成對之節點[1 ] 側的葉節點之索引鍵，由於耦合節點樹之順序性，係全部 爲較分割鍵爲大。故而，在現在之例的情況中，在以較分 割鍵爲更上位之分支節點作爲根節點的部分樹中，分割鍵 係不可能成爲最大値，因此，分割鍵係爲分割節點樹之最 大値，分割節點樹係爲將分割鍵作爲最大値之處理源頭的 部分樹中之最大者。 若是將分割鍵作爲索引鍵而包含的葉節點係爲節點 [1 ]，則只要對樹以節點[1 ]側來作探索，則由於耦合節點 樹之順序性，在任何之以節點[1 ]作爲根節點的部分樹中 ，上述分割鍵係均爲此些之部分樹的最大値。與此葉節點 成對之存在於節點[1 ]側的葉節點之索引鍵，由於耦合節 點樹之順序性，係全部較分割鍵爲大。而，當探索至節點 [〇]爲止時，在較此而更爲上位之節點的下位處，係存在 有與該當節點[〇]成對之節點[1 ]以下的節點，在此些之節 點中，係存在著包含有較上述分割鍵爲更大的索引鍵之葉 節點。 故而，以上述節點[0]亦即是，以分割節點作爲根節 點的部分樹，係爲將上述分割鍵作爲最大値而包含的最大 -55- 200834356 之部分樹。 以下，接著參考圖20以下，而進行分割處理之說明。 圖20，係爲展示身爲在圖17所示的步驟S004中之處 理目標的根節點之插入處理之處理流程的圖。 在步驟S2001中，係將儲存有在圖17中所示之處理流 程的步驟S002所求取之分割節點的配列要素之配列號碼 ，設定爲插入節點之配列號碼。

接下來，在步驟S2 003中，從配列中而取得空的節點 對之代表節點號碼。 接下來，在步驟S2004中，將在步驟S2003中所取得 之代表節點號碼，作爲節點[〇]之配列號碼而設定。 接下來，在步驟S2005中，將在步驟200 1中所設定之 插入節點的配列號碼所指向之配列要素的內容讀出，並儲 存在以步驟S2004所設定之節點[〇]之配列號碼所指向的配 列要素中。 最後，在步驟S2009中，將節點[0]之配列號碼作爲處 理目標之根節點之配列號碼而登錄，並結束根節點之插入 處理。 在圖30A以及圖30B之（b)的例示中，儲存有分割節點 2 1 Of之配列要素的配列號碼22 1 b，係被設定爲插入節點 之配列號碼，而所取得之空的節點對20 1 i之代表節點號碼 220’ ’係作爲節點[〇]之配列號碼而被設定。 而後，配列號碼22 1 b所指向之配列要素的內容，亦 即是分割節點2 1 Of之內容，係被儲存在配列號碼220，所指 -56- 200834356 向之配列要素，亦即是被儲存在節點2 1 Oi中，而配列要素 220 ’’係作爲處理目標之根節點的配列要素而被登錄。 圖21，係爲展示在圖17所示的步驟S005中之藉由分 割鍵與處理目標的最小値而求取出差分位元位置之處理流 程的圖。 如圖21所示一般，在步驟S2 101中，將處理目標之根 節點的配列號碼，作爲檢索開始節點之配列號碼而設定之 接下來，在步驟S2 102中，實行於圖5中所示之最小 値檢索，並得到處理目標之索引鍵的最小値。 接下來，在步驟S2 103中，將在圖17所示之步驟SO 10 中所設定的分割鍵與在步驟S2 1 03中所得到之最小値進行 位元列比較，並求取出從上位第0位元起所見到之最初的 不一致位元位置，而作爲差分位元位置來設定。

另外，在上述步驟S21 01中，雖係將處理目標之根節 點的配列號碼，作爲檢索開始節點之配列號碼而設定，但 是，由於明顯的，在最後所插入之處理目標中之分割節點 樹中，係包含有處理目標之最小値，因此，藉由將最後所 插入之分割節點，例如在圖30B之（b)中所例示的處理目 標中，將節點2 1 0j之配列號碼220j作爲檢索開始節點之 配列號碼而設定，能夠減輕最小値檢索之處理。 圖22，係爲說明在圖17所示的步驟S006中之根節點 以外的對處理目標之插入處理之處理流程的圖。 最初，在步驟S220 1中，係將儲存有在圖I7中所示之 -57- 200834356 處理流程的步驟S008中所求取之分割節點的配列要素之 配列號碼，作爲插入節點之配列號碼而設定之。此步驟 S2201，相較於在圖20所示之步驟S2001，僅在求取分割 節點之處理步驟係爲步驟S0 08之點上爲相異。 接下來，在步驟S2202中，作爲處理目標之插入位置 ，設定根節點之配列號碼。

接下來之步驟S2203〜步驟S2205中，係與圖20所示 之根節點的插入處理之步驟S 2 0 0 3〜步驟S 2 0 0 5相同。 在步驟S2203中，從配列中，取得空的節點對之代表 節點號碼，接下來，在步驟S2204中，將在步驟S2203中 所取得之代表節點號碼，設定爲節點[0]之配列號碼，接 下來，在步驟S2205中，將在步驟S220 1中所設定之插入 節點的配列號碼所指向之配列要素的內容讀出，並儲存在 以步驟S2204所設定之節點[〇]的配列號碼所指向之配列要 素中。 接下來，前進至步驟S2206，將在步驟S2203中所取 得之代表節點號碼上加算上値“ 1 ”之後的値，作爲節點[1 ] 之配列號碼而設定。 接下來，在步驟S2007中，將在步驟2202中所設定之 處理目標之插入位置的配列號碼所指向之配列要素的內容 讀出，並儲存在以步驟S2006所設定之節點[1]之配列號碼 所指向的配列要素中。 最後，在步驟S221 8中，在節點種類別中設定分支， 在辨別位元位置中設定以圖1 7所示之步驟S 0 0 5所求取的 -58 - 200834356 辨別位元位置，在代表節點號碼中設定以步驟S2204所設 定之節點[〇]的配列號碼，而形成分支節點，並儲存在以 步驟S2202所設定之處理目標的插入位置之配列號碼所指 向的配列要素中，而結束處理。

在圖30B以及圖30C之例示中，儲存有分割節點210b 之配列要素的配列號碼220a，係被設定爲插入節點之配列 號碼，而作爲處理目標之插入位置，係設定有根節點2 1 0i 之配列號碼220’。又，所取得之空的節點對201j之代表節 點號碼22 Oj，係作爲節點[0]之配列號碼而被設定。 而後，插入節點之配列號碼220a所指向之配列要素 的內容，亦即是分割節點2 1 Ob之內容，係被儲存在節點 [〇]之配列號碼220j所指向之配列要素，亦即是被儲存在 節點21 Oj中。 另一方面，身爲在代表節點號碼220j上加上1後所得 到之値的配列號碼220j + l所指向的配列要素中，亦即是節 點2 11 j中，係被儲存有處理目標之插入位置的配列號碼 220’所指向之配列要素、亦即是圖30B之（b)中所示之根節 點21 0i的內容。 而，在圖30C之（b)所示的根節點210i之辨別位元位 置2 3 0 i中，係儲存有在關於先前之圖1 7的步驟S 0 0 5之例 示中所說明的身爲分割節點樹292之最大値的索引鍵 25 lc“0 1 1〇1〇”、與身爲處理目標之最小値的索引鍵 2 5 0g“1 0 00 1 0”，其兩者間的差分位元位置“ 0” 。又，在 代表節點號碼中’係被儲存有節點[0]之配列號碼220j。 -59— 200834356 如同由上述說明而能夠理解一般，在產生插入目標後 之插入處理，係在插入目標之根節點的正下方，插入由分 支節點彼此所成之節點對，並在該節點對之節點[1 ]以下 ，連接上既存之處理目標的根節點以下之部分樹’並在節 點[〇]處，連接上分割節點樹者。藉由此處理’明顯的， 在將分割節點樹插入後之插入目標的順序性係被保持。

圖23，係爲展示在圖17所示的步驟S007中之分割節 點樹的削除處理之處理流程的圖。同樣的，在削除處理中 ，雖亦係有類似之點，但是，相對於圖1 6所示之削除處理 係將身爲儲存有削除鍵之葉節點的削除節點作削除，在圖 23中所示者，基本上係將身爲分支節點之分割節點削除， 而從處理源頭，以該分割節點作爲根節點之分割節點樹係 被削除。 首先，在步驟S23 0 1中，係將儲存有在圖17中所示之 步驟S002中或是步驟S008中所求取之分割節點的配列號 碼，作爲處理源頭之削除節點的配列號碼而設定之。 接下來，判定在步驟S2301中所設定之削除節點的配 列號碼，是否與處理源頭之根節點的配列號碼一致。當削 除節點之配列號碼，係與處理源頭之根節點的配列號碼一 致時，則前進至步驟S2303，將處理源頭之根節點的代表 節點號碼所指向之節點對削除，接下來，在步驟S2304中 ，將處理源頭之根節點的配列號碼之登錄抹除，而結束處 理。 步驟S2302之判定處理的結果，當削除節點之配列號 • 60- 200834356 碼與處理源頭之根節點的配列號碼爲不一致時’則前進至 步驟S2 305，求取出與在步驟S2 301中所設定之削除節點 成對的節點之配列號碼，並作爲對節點之配列號碼而設定

接下來，在步驟S2306中，從處理源頭之探索路徑堆 疊中取出配列號碼，並將該所取出之配列號碼，作爲在步 驟S23 07中之母節點的配列號碼而設定，同時，使母節點 之代表節點號碼暫時退避至他處。另外，在處理源頭之探 索路徑堆疊中，係藉由圖19所示之步驟S 1 902或是於後所 說明之圖24所示之步驟S2402的處理，而被儲存有身爲分 割節點之近旁上位的母節點之配列號碼。 接下來，在步驟S2308中，將在步驟2305中所設定之 對節點的配列號碼所指向之配列要素的內容讀出，並儲存 在以步驟S2 3 07所設定之母節點的配列號碼所指向之配列 要素中。 最後，在步驟S2309中，將在步驟S2307中所暫時退 避至他處之母節點的代表節點號碼所指向之節點對削除， 並結束處理。 圖24，係爲展示在圖1 7所示的步驟S 00 8中之求取下 一個分割節點的處理之處理流程的圖。 在步驟S2401中，判定處理源頭之探索經路堆疊的堆 疊指標是否指向根節點之配列號碼。若是處理源頭之探索 路徑堆疊的堆疊指標係指向根節點之配列號碼，則送回「 無分割節點」。 -61 - 200834356 若是探索路徑堆疊之.堆疊指標係並非指向根節點的配 列號碼’則前進至步驟S2402，並從探索路徑堆疊中取出 配列號碼，而將探索路徑堆疊之堆疊指標減去1個。 接下來，前進至步驟S2403中，從以步驟S2402所取 出之配列號碼中，得出被配置在此配列號碼所指向之配列 要素中的節點之節點位置。

接下來，在步驟S2404中，判定在步驟S2403中所得 到之節點位置是否爲節點[〇 ]側。判定之結果，若是爲節 點[〇]側’則回到步驟S2401之處理，若是爲節點⑴側， 則移動至步驟S 2 4 0 6，將從在步驟S 2 4 0 2中所取出之配列 號碼處減去値1後所得到之節點[〇]之配列號碼，作爲分割 節點之配列號碼而設定，並送回「有分割節點」。 在圖30Α及圖30Β之例示中，在求取出下一個分割節 點的階段中，由於處理源頭之探索路徑堆疊的堆疊指標， 係指向身爲分割節點210f之母節點的配列號碼之220 a+1 ，而節點位置係成爲節點[1 ]側，因此，與此成對之位置 於節點[〇]側的節點2 1 Ob，係成爲下一個分割節點，而身 爲儲存有此之配列要素的配列號碼之220a，係作爲分割節 點之配列號碼而被設定。 又，在圖30B及圖30C之例示中，在更進一步求取接 下來之分割節點的階段中，由於處理源頭之探索路徑堆疊 的堆疊指標係指向身爲節點2 1 Ob之母節點的根節點2 1 〇a 之配列號碼220，因此，上述步驟S2401之判定處理的結 果係送回「無分割節點」。亦即是，若是分割節點之母節 -62- 200834356 點係成爲根節點，則下一個分割節點係不存在。此事，從 耦合節點樹之順序性來看，係爲當然。 圖25，係爲展示求取出以在圖17所示的步驟S008所 求取之分割節點作爲根節點的分割節點樹之最大値，並作 爲下一個分割鍵的步驟S 〇 1 0之處理流程的圖。

首先，在步驟S250 1中，使處理源頭之探索經路堆疊 的堆疊指標之値暫時退避至他處。其理由，係因爲經由在 圖19所示之步驟 S1902，或是經由在圖24所示之步驟 S24 02之處理，分割節點之母節點的配列號碼所指向之處 理源頭的堆疊指標之値，係會因爲後述之步驟S2503的最 大値檢索而變動，而變得無法在圖23所示之步驟S2306中 來使用之故。 接下來，在步驟S2502中，將在圖24之步驟S2406中 所設定之分割節點的配列號碼，作爲檢索開始節點之配列 號碼而設定。 而後，在步驟S2 5 03中，實行於圖6中所示之最大値 檢索，並求取出索引鍵的最大値。 接下來，前進至步驟S2504，將在步驟S2502中所得 到之最大値是否，作爲分割鍵而設定。 最後，在步驟S2505中，將在步驟S250 1中所暫時退 避至他處的値，作爲處理源頭之探索路徑堆疊的堆疊指標 之値而復原，並結束處理。 以上，如同從參考.圖24及圖25而詳細說明後可理解一 般，在圖17之步驟S008中所求取之下一個分割節點，與 -63- 200834356 在步驟S010中所求取之下一個分割鍵間之關係’係與在 先前所說明之步驟001所設定之分割鍵與在步驟S002所求 取之分割鍵、或是分割節點樹間之關係爲相同。

可以明白，在上述步驟S010所求取之下一個分割鍵 ，係爲以在步驟s 0 0 8所求取之下一個分割鍵作爲根節點 之分割節點樹的最大値。又，由於在步驟S008所求取之 下一個分割節點，係爲節點[〇]，因此，由耦合節點樹之 順序性，可以明顯得知，將較此爲更上位之節點作爲根節 點的部分樹，係包含著儲存有較在步驟S010中所求取之 下一個分割鍵爲更大的索引鍵之葉節點。 雖藉由以上，而針對實施例3所致之耦合節點樹的分 割處理作了詳細說明，但是，若藉由實施例3，則係以分 割耦合節點樹單位來進行分割處理。亦即是，將分割節點 從處理源頭而分割，並將分割節點之對節點複製至母節點 中，藉由此，分割節點樹係從處理源頭而被削除，並藉由 將分割節點插入至處理目標中，而完成分割節點樹之插入 故而，只要是使用相同之配列，則對於分割節點以外 之節點的處理係成爲不必要，相較於實施例2的情況，處 理的實行步驟係能夠變得更少。 接下來，針對於分割處理同樣地以部分樹單位來進行 處理之實施例3所致的耦合節點樹之結合處理作說明。本 實施例之結合處理，係和實施例1以及實施例2之結合處理 大不相同，相對於實施例1以及實施例2之結合處理係以索 -64- 200834356 引鍵單位，換言之，係以節點單位來進行結合處理，本實 施例係爲將滿足特定之條件的部分樹單位從處理源頭分割 並結合至處理目標處者。相對於在實施例1與實施例2之結 合處理中，係藉由對分割鍵作選擇，而將分割處理直接作 適用，若是如同本實施例一般地以部分樹單位來進行結合 處理，則無法將分割處理單純地作適用。

此係因爲，處理源頭以及處理目標，係分別具備有因 應於被儲存在其內部之索引鍵的差分位元位置之構造，因 此，並不一定能夠將處理源頭本身作爲分割節點樹而直接 插入至處理目標中。 圖26，係爲說明在實施例3中之耦合節點樹的結合處 理流程之圖。在以下之說明中，雖係將處理目標之索引鍵 設爲較處理源頭之索引鍵爲更大，但是，由下述之說明， 應可容易地理解，就算是在相反的狀況下，亦同樣的可進 行處理。 圖3 1 A〜圖3 1 C，係爲將上述結合處理藉由實例來作 說明之圖，並例示有與在圖2B中所例示之耦合節點樹之 部分樹相類似之樹。 圖31A，係爲展示結合處理開始前之處理源頭與處理 目標之樹的構造例之圖。在圖31 A之（a)中，係例示有處 理源頭，此係展示有··身爲於其配列號碼被附加有符號 220a+ 1之分割結合節點與以其作爲根節點之部分樹，而成 爲結合處理之單位的部分樹之分割結合節點樹293。以後 ，係有將表示節點之符號，以在藉由檢索處理而探索至該 -65- 200834356 節點時’被堆疊在探索路徑堆疊中之該節點所被配置的配 列要素之配列號碼來作表示的情形。 在圖3 1 A之（b)中，係例示有處理目標，而成爲結合 位置之節點，係附加有該配列號碼之符號22〗f而被表示 。又’在圖3 1 A中’係亦展示有··處理源頭之最大値係爲 索引鍵25 lg之“101001”，而處理目標之最小値係爲索引 鍵 25 Oh 之 “10101 1”。

圖31B，係爲展示有將在圖31A中所示之分割結合耦 合節點樹2 9 3插入至處理目標中，並將其從處理源頭削除 後的樹構造之圖，在圖31B之（a)中，處理源頭之下一個分 割結合節點樹2 94，係被以點線來包圍而展示，並顯示有 :最大値係爲索引鍵251d之“011010”。在圖31B之（b)中 ’係分別將處理目標之被結合的分割節點樹293、藉由結 合處理所追加之節點對201k與節點221f之連結關係，以 點線來包圍而展示，並展示有：下一個結合位置係爲節點 221° 圖31C’係爲展不有將在圖31B中所不之分割結合節 點樹294插入至處理目標中，並將其從處理源頭削除後的 樹構造之圖。由於在圖3 1 B之（a)中所示的處理源頭之下一 個分割結合節點220係爲根節點，因此，處理源頭之根節 點係被削除，在圖3 1 C之（a)中，係並未表示有任何東西。 在圖31C之（b)中，係分別將處理目標之被結合的分割節 點樹294、藉由結合處理所追加之節點對201m與節點221 之連結關係，以點線來包圍而展示。 •66- 200834356 以下，對圖1 5以及圖3 1 A〜圖3 1 C作參考，而對本實 施例之結合處理的槪要作說明。

在圖2 6之步驟S 2 6 0 1中，求取出處理源頭之最大値與 處理目標之最小値的差分位兀位置。在圖31A之例不中， 係求取出有處理源頭之最大値“ 1 0 1 00 1”與處理目標之最小 値“101011”的差分位元位置4。求取差分位元位置之處理 的詳細，係於後參考圖27而作說明。另外，在以下之說明 中，係亦有將在此步驟S260 1中所求取之差分位元位置單 純稱爲差分位元位置的情形。 接下來，在步驟S2602中，藉由在步驟S260 1所求取 出之差分位元位置，來求取出處理源頭之分割結合節點。 在圖31A之例示中，係求取出有分割結合節點220a+Ι。對 此處理的詳細內容，係於後參考圖2 8而作說明。 接下來，前進至步驟S2603中，藉由在步驟S2601所 求取出之差分位元位置，來求取出用以將在步驟S2602中 所求取出之分割結合節點作插入之處理目標的結合位置。 在圖31A之例示中，係求取出有結合位置22 If。對此處理 的詳細內容，係於後參考圖29而作說明。 接下來，在步驟S2604中，在步驟S2603所求取出之 結合位置處，插入在步驟S2602中所求取出之分割結合節 點。此處理，係可藉由在參考圖22而作了說明之插入處理 中，作爲步驟S2201之插入節點的配列號碼，設定在步驟 S2 602中所求取之分割結合節點的配列號碼，並在步驟 S22 02之處理目標的插入位置中，設定在步驟S2603中所 -67- 200834356 求取出之結合位置的配列號碼，並實行該插入處理，而實 現之。

在圖31A以及圖31B之例示中，在圖22之步驟S220 1 中，係將分割結合節點220a+l之配列號碼220a+l，設定於 插入節點設定區域中，而在步驟S22 02中，在插入位置設 定區域中，設定結合位置22 1 f之配列號碼22 1 f。接下來， 在步驟S2203中，取得空的節點對201k，將該代表節點號 碼220k，在步驟S2004中，作爲節點[0]之配列號碼而設定 而後，在步驟S2205中，將被設定於插入節點設定區 域中之配列號碼22〇a+ 1所指向之配列要素的內容，亦即是 分割節點221b之內容讀岀，並儲存在作爲節點[0]之配列 號碼而被設定之配列號碼220k所指向之配列要素，亦即 是被儲存在節點210k中。 進而，在步驟S2206中，將身爲在代表節點號碼220k 上加上了 1後之値的22Ok+1，作爲節點[1]之配列號碼而設 定。而後，將在步驟S2207中，被作爲插入位置而設定之 配列號碼22 0 1 f所指向之配列要素’亦即是節點2 1 Oh之內 容讀出，並儲存在作爲節點[1 ]之配列號碼而被設定之配 列號碼220k+l所指向之配列要素，亦即是儲存在節點21 Ik 中〇 最後，在步驟S2208中，在作爲插入位置而被設定之 配列號碼22 1 f所指向的配列要素’亦即是節點2 1 Oh之位 置中，將節點種類別設爲0，將辨別位元位置設爲於圖2 6 -68- 200834356 之步驟S2 6 0 1中所求取之差分位元位置4，將代表節點號 碼設爲作爲節點[0]之配列號碼而設定之配列號碼220k， 而產生新的分支節點，而得到了圖3 1 B之（b)中所示之結 合後的處理目標之構造。

接下來，若是回到圖26所致之樹結合處理的說明，則 在步驟S2605中，從處理源頭而將分割結合節點削除。此 處理，係可藉由在參考圖23而作了說明的削除處理中，將 分割節點代換讀取爲分割結合節點並實行而實現之。 接下來，前進至步驟S2606，判定處理源頭是否有被 登錄。若是有被登錄，則回到步驟S2601，並反覆進行處 理，若是未被登錄，則由於結合處理係已結束，故結束處 理。 接下來，——面參考圖27〜圖29，一面對本實施例之結 合處理作詳細說明。 圖27，係爲展示在圖26所示的步驟S2 601中之求取差 分位元位置的處理之詳細處理流程的圖。首先，在步驟 S2701中，將處理源頭之根節點的配列號碼，作爲檢索開 始節點之配列號碼而設定之。接下來，在步驟S2702中， 藉由於圖6中所示之檢索處理，而求取出處理源頭之索引 鍵的最大値。 接下來，前進至步驟S2703中，將處理目標之根節點 的配列號碼，作爲檢索開始節點之配列號碼而設定之。接 下來，在步驟S27 04中，藉由於圖5中所示之檢索處理， 而求取出處理目標之索引鍵的最小値。 -69- 200834356 接下來，在步驟S2705中，將在步驟S2702中所求取 的最大値，與在步驟S2704中所求取之最小値進行位元列 比較，並求取出從上位第0位元起所見到之最初的不一致 位元位置，而作爲差分位元位置來設定，並結束處理。

如同先前所述一般，在圖31A之例示中，係求取出有 處理源頭之最大値“ 1 0 1 0 0 1”與處理目標之最小値“ 1 0 1 0 1 1，， 的差分位元位置4。而，在處理源頭與處理目標中，均並 不存在有辨別位元位置與此差分位元位置爲相等之分支節 點。 此係因爲，由於相較於處理源頭之最大値，處理目標 之最小値係爲更大，因此，處理源頭之最大値的差分位元 位置的位元値係爲0，如果，在處理源頭之分支節點中， 存在有辨別位元位置與差分位元位置爲相等者，則處理源 頭之最大値係成爲節點[〇]，而會與身爲最大値一事產生 矛盾之故。關於處理目標，亦爲相同。 接下來’說明求取處理源頭之分割結合節點的處理。 分割結合節點’除了處理源頭係僅存在有根節點的例外之 外’係爲在以最大値檢索所探索之分支節點中，辨別位元 位置爲較在圖26所示之步驟S 26 01中所求取出之差分位元 位置爲更下位者之中，身爲最上位之分支節點。 若是將以分割結合節點作爲根節點之處理源頭的部分 樹，稱爲分割結合節點樹，則本實施例之結合處理，係爲 以分割結合節點樹單位而進行結合處理者。 圖2 8 ’係爲對圖2 6所示的步驟s 2 6 0 2之求取處理源頭 -70- 200834356 的分割結合節點之處理流程作說明的圖。另外，在求取分 割結合節點之處理的開始時，處理源頭之探索路徑堆疊的 堆疊指標，係指向在圖26所示之步驟S2601中的最大値檢 索之結果，亦即是，係指向儲存有索引鍵之最大値的葉節 點之配列號碼。

在步驟S2801中，判定處理源頭之探索經路堆疊的堆 疊指標是否指向根節點之配列號碼。當處理源頭之探索路 徑堆疊的堆疊指標係指向根節點之配列號碼的情況時，係 前進至步驟S 2 8 1 0，當處理源頭之探索路徑堆疊的堆疊指 標係並非指向根節點之配列號碼的情況時，則係前進至步 驟 S2802 〇 在步驟S2802中，係將探索路徑堆疊之堆疊指標倒退 一個’並取出該堆疊指標所指向的配列號碼，而前進至步 驟 S2803 。 在步驟S2803中，係將在步驟S2802中所取出之配列 號碼所指向的配列要素之內容作爲節點而取出，並在步驟 S2 3 04中，取得所取出之節點的辨別位元位置。 接下來，在步驟S2805中，判定以步驟S2804所取得 之辨別位元位置是否爲較差分位元位置更上位之位置關係 。若是爲下位，則回到步驟S280 1，若是爲上位，則前進 至步驟S2809。如同先前所述一般，並不會有上述之辨別 位元位置與差分位元位置成爲相<等的情況。 在步驟S2809中，係將處理源頭之探索經路堆疊的堆 疊指標前進一個，並移動至步驟S2810。 -71 - 200834356 在步驟S2810中’從處理源頭之探索路徑堆疊中，將 堆疊指標所指向的配列號碼取出，並作爲處理源頭之分割 結合節點的配列號碼而設定，而結束處理。另外，在以下 之說明中，亦有將於此所設定之配列號碼，單純稱爲分割 結合節點之配列號碼的情況。 若是將上述處理參考圖3 1 A以及圖3 1 B而作說明，則 係爲如下所示一般。

在圖3 1 A之例示中，若是從儲存有鍵之最大値的節點 2 1 1 g起，對探索路徑作探索，則一開始，由於堆疊指標 係指向節點21 lg之配列號碼221b，因此，步驟S280 1之判 定係成爲「否」，而反覆進行從步驟S2801起之處理，由 於差分位元位置係爲4，因此，在步驟S 2 8 0 2之處理中， 係到達了根節點2 1 0a，而由於根節點2 1 0a之辨別位元爲 係爲〇，且爲較差分位元位置爲更上位，因此，在步驟 S 2 8 0 5之判定處理中，係分歧至步驟 s 2 8 0 9，藉由步驟 S 2 8 0 9之處理，將探索路徑前進1個，而求取出分割結合節 點 220a+l 。 在圖3 1 B之例示中，若是從儲存有鍵之最大値的節點 211d起’對探索路徑作探索，則由於差分位元位置係爲〇 ，因此，在步驟S28 02之處理中，係到達了根節點21〇a， 而由於根節點2 1 0a之辨別位元爲係爲1，且爲較差分位元 位置爲更下位，因此，在步驟S2 8 05之判定處理中，係分 歧至步驟S 2 8 0 1，藉由步驟S 2 8 0 1之判定處理，係被判定 爲根節點，而分歧至步驟S2810，將根節點210a，作爲下 -72- 200834356 一個分割結合節點而求取出來。

接下來，說明求取處理目標之結合位置的處理。在結 合處理後之處理目標中，由於係被插入儲存有索引鍵之最 大値的葉節點，因此，係新存在有具備與差分位元位置相 等之値的辨別位元位置之分支節點。亦即是，係成爲將具 備有與差分位元位置相等之値的辨別位元位置之分支節點 ’插入至在最小値檢索中所探索了的路徑中，而將此插入 位置作爲處理目標之結合位置。 在耦合節點樹中，下位之分支節點的辨別位元位置， 由於係爲較上位之分支節點的辨別位元位置爲更下位，因 此，具備較差分位元位置爲更近旁上位之辨別位元位置的 分支節點之子節點的位置，係成爲結合位置，或是，若是 例外地不存在有具備上位之辨別位元位置的分支節點，則 根節點係成爲結合位置。 在被插入至結合位置中之分支節點的子節點對之節點 [1 ]側中，係存在著儲存有結合前之處理目標的索引鍵之 最小値的葉節點，而節點[〇]係爲分割結合節點。 圖2 9，係爲說明求取上述處理目標之結合位置的處理 流程之圖。如圖29所示一般，求取處理目標之結合位置的 處理流程，係爲和在圖28中所示之求取處理源頭之分割結 合節點的處理流程爲相同的構造。圖29之處理流程，係爲 關於處理目標者，而僅在所求取者係爲結合位置一事上係 爲相異。另外’在求取處理目標之結合位置之處理的開始 時’處理目標之探索路徑堆疊的堆疊指標，係指向在圖2 6 -73- 200834356 所示之步驟S2601中的最小値檢索之結果，亦即是，係指 向儲存有索引鍵之最小値的葉節點之配列號碼。 在步驟S2901中，判定處理目標之探索路徑堆疊的堆 疊指標是否指向根節點之配列號碼。當處理目標之探索路 徑堆疊的堆疊指標係指向根節點之配列號碼的情況時，係 前進至步驟S2910，當處理目標之探索路徑堆疊的堆疊指 標係並非指向根節點之配列號碼的情況時，則係前進至步

驟 S2902 〇 在步驟S2902中，係將探索路徑堆疊之堆疊指標倒退 一個，並取出配列號碼，而前進至步驟S29 03。 在步驟S2903中，係將在步驟S2902中所取出之配列 號碼所指向的配列要素之內容作爲節點而取出，並在步驟 S 29 04中，取得所取出之節點的辨別位元位置。 接下來，在步驟S2905中，判定以步驟S2904所取得 之辨別位元位置是否爲較差分位元位置更上位之位置關係 。若是爲下位，則回到步驟S2 90 1，若是爲上位，則前進 至步驟S2909。如同先前所述一般，並不會有上述之辨別 位元位置與差分位元位置成爲相等的情況。 在步驟S2909中，係將處理源頭之探索經路堆疊的堆 疊指標前進一個，並移動至步驟S2910。 在步驟S2910中，從處理目標之探索路徑堆疊中，將 堆疊指標所指向的配列號碼取出，並作爲處理目標之結合 位置的配列號碼而設定，而結束處理。另外，在以下之說 明中，亦有將於此所設定之配列號碼，單純稱爲結合位置 -74- 200834356 之配列號碼的情況。 若是將上述處理參考圖31A以及圖31B而作說明，則 係爲如下所示一般。

在圖3 1 A之例示中，若是從儲存有鍵之最小値的節點 2 1 Oh起，對探索路徑作探索，則由於差分位元位置係爲4 ，且藉由步驟S2904所取出之根節點21 Of的辨別位元位置 係爲3，因此，從步驟S2905起，分歧至步驟S2909，藉由 步驟S2909之處理，將探索路徑堆疊前進1個，而求取出 結合位置之配列號碼221 f。 在圖3 1 B之例示中，若是從儲存有鍵之最小値的節點 2 1 〇g起，而對探索路徑作探索，則由於差分位元位置係 爲〇，因此，係到達根節點21 Of，並在步驟S2901中，被 判定出其係爲根節點，而分歧至步驟S 2 9 1 0，並將根節點 2 1 Of之配列號碼22 1，作爲下一個結合位置之配列號碼而 求取出來。 雖藉由以上’而針對實施例3所致之耦合節點樹的結 合處理作了詳細說明，但是，若藉由實施例3，則係以分 割結合節點樹單位來進行結合處理。亦即是，將分割結合 節點從處理源頭而分割，並將分割結合節點之對節點複製 至母節點中，藉由此，分割結合節點樹係從處理源頭而被 削除，並藉由將分割結合節點結合於處理目標，而完成分 割結合節點樹之結合。 故而，只要是使用相同之配列，則對於分割結合節點 以外之節點的處理係成爲不必要，相較於實施例2的情況 -75- 200834356 ，處理的實行步驟數係能夠變得更少。 以上。雖係對用以實施本發明之最佳實施形態作了說 明，但是，同業者應可清楚明白，本發明之實施形態係並 不限定於此，而可作各種之變形。

明顯的，藉由將以上所說明之本發明的實施形態所致 之賴合節點樹之分割結合處理以及與此些均等之物於電腦 上實行的程式’能夠實現本發明之耦合節點樹之分割方法 以及結合方法。 故而’上述程式、以及記憶有程式而爲電腦可讀取之 記憶媒體，係亦包含於本發明之實施形態內。 【圖式簡單說明】 [圖1]展示在先前之檢索中所使用的帕翠西雅樹之其 中一^例的圖。 [圖2A]說明被儲存於配列中之耦合節點樹的構成例之

[圖2B]將耦合節點樹之樹狀構造作槪念展示的圖。 [圖3 ]說明用以實施本發明之硬體的構成例之圖。 [圖4]展示位元列檢索的基本動作之流程圖。 [圖5]展示求取出被儲存於耦合節點樹中之索引鍵的 最小値之處理的流程圖。 [圖6]展示求取出被儲存於耦合節點樹中之索引鍵的 最大値之處理的流程圖。 [圖7A]展示求取索引鍵的下限値之處理的前段之流程 -76 - 200834356 圖。 [圖7B]展示求取索引鍵的下限値之處理的後段之流程 圖。 [圖8 A]展示求取索引鍵的上限値之處理的前段之流程 圖。 [圖8B]展示求取索引鍵的上限値之處理的後段之流程 圖。

[圖9A]展示身爲插入處理之前段的檢索處理之處理流 程的圖。 [圖9B]說明將插入之節點對所需要的配列要素作準備 之處理的處理流程圖。 [圖9C]展示對插入節點對之位置作求取，並將節點對 之各節點的內容作寫入，而完成插入處理之處理流程的圖 [圖1 0]對將包含有根節點之插入處理的索引鍵作追加 時之節點插入處理全體作說明的處理流程圖。 [圖1 1 A]展示身爲削除處理之前段部分的檢索處理之 處理流程的圖。 [圖11B]說明削除處理之後段的處理流程之圖。 [圖1 2]說明在實施例1中之耦合節點樹的分割處理流 程之圖。 [圖1 3]說明在實施例2中之耦合節點樹的分割處理流 程之圖。 [圖1 4]說明在實施例2中之節點的插入處理流程之圖 -77- 200834356 [圖1 5 A ]說明在實施例2中之根節點設定處理的流程圖 [圖15B]說明在實施例2中之在母節點中將包含有插入 鍵的節點對作插入之處理流程之圖。 [圖1 6 ]說明在實施例2中之削除處理的流程圖。

[圖1 7]說明在實施例3中之耦合節點樹的分割處理流 程之圖。 [圖18]說明在求取最初之分割節點的處理流程之前段 的圖。 [圖1 9 ]說明在求取最初之分割節點的處理流程之後段 的圖。 [圖20]說明處理目標之根節點的插入處理之處理流程 的圖。 [圖2 1 ]對分割處理中之求取差分位元位置之處理流程 作說明的圖。 [圖22]說明根節點以外之插入處理的處理流程之圖。 [圖23]說明在實施例3中之削除處理的處理流程之圖 [圖24]說明求取下一個分割節點之處理的處理流程之 圖。 [圖25]說明求取分割節點樹之最大値，並作爲下一個 分割節點之處理的處理流程之圖。 [圖26]說明在實施例3中之耦合節點樹的結合處理流 -78- 200834356 程之槪要的圖。 [圖27]對結合處理中之求取差分位元位置之處理流程 作說明的圖。 [圖2 8 ]說明求取處理源頭之分割結合節點的處理流程 之圖。 [圖29]說明求取處理目標之結合位置的處理流程之圖

[圖3 0 A]對分割前之樹構造例作說明的圖。 [圖3 0B]對最初之分割後之樹構造例作說明的圖。 [圖3 0C]對接下來之分割後之樹構造例作說明的圖。 [ffl 3 1 A]對最初之結合處理前之樹構造例作說明的圖 [Β 3 1 Β]對最初之結合處理後之樹構造例作說明的圖 [Η 3 1 C]對接下來之結合處理後之樹構造例作說明的

【主要元件符號說明】 3 〇 1 :資料處理裝置 3〇2 :中央處理裝置 3〇3 :快取記憶體 3〇4 :匯流排 3〇5 :主記憶裝置 3〇6 :外部記憶裝置 -79- 200834356

3 07 :通訊裝置 3 08 :資料儲存裝置 3 09 :配列 3 1 0 :探索路徑堆疊 -80-

Claims (1)

1. 200834356 十、申請專利範圍

   1 · 一種耦合節點樹之分割方法，該耦合節點樹，係由 根節點（root node)、與被配置於相鄰接之記憶區域中的分 支節點（branch node)與葉節點（leaf node)、又或是分支節 點彼此又或是葉節點彼此之節點對所成的使用於位元列檢 索之樹（tree)，並具有以下構成：前述根節點，係爲表示 樹之起點的節點，當該樹之節點係爲1個時，係身爲前述 葉節點，而當該樹之節點係爲2個以上時，則係爲前述分 支節點，前述分支節點，係包含有表示進行位元列檢索之 檢索鍵的辨別位兀位置、以及身爲連接（link)目標之節點 對的其中一方之節點的代表節點之位置之位置資訊，前述 葉節點，係包含有由檢索對象之位元列所成的索引鍵 (index key)， 將前述樹之任意的節點作爲檢索開始節點，在前述分 支節點中，因應於被包含在該分支節點中之辨別位元位置 之檢索鍵的位元値，而對連結目標之節點對的代表節點或 者是被配置於與其相鄰接之記憶區域中的節點作連結，並 依序反覆進行此，直到到達前述葉節點爲止，藉由此，將 被儲存於前述葉節點中之索引鍵，作爲身爲在將前述檢索 開始節點作爲根節點之前述耦合樹的任意之部分樹的前述 檢索鍵所致之檢索結果的檢索結果鍵， 該分割方法，其特徵爲，具備有以下步驟： 分割鍵取得步驟，係取得對將身爲分割對象之處理源 頭耦合節點樹作分割之索引鍵作決定的分割鍵；和 -81 - 200834356 處理源頭最小値或最大値取得步驟，係求取出前述處 理源頭耦合節點樹之索引鍵的最小値或者是最大値；和

   比較步驟，係對前述分割鍵與前述最小値或者是最大 値間之大小作比較，若是該最小値係較前述分割鍵爲更大 ，或是該最大値係較前述分割鍵爲更小，則結束處理；和 產生步驟，當前述比較之結果，該最小値係並未較前 述分割鍵爲更大，或是該最大値係並未較前述分割鍵爲更 小，則藉由將該最小値或者是該最大値之索引鍵插入，而 產生新的處理目標耦合節點樹；和 削除步驟，係從前述處理源頭耦合節點樹中，將前述 最小値或者是前述最大値之索引鍵削除， 將削除了前述最小値或者是前述最大値之索引鍵的前 述處理源頭耦合節點樹，作爲新的處理源頭耦合節點樹之 前述處理源頭最小値或是最大値取得步驟、前述比較步驟 '前述產生步驟、以及前述削除步驟，反覆進行此些，直 ©I以前述處理源頭最小値或是最大値取得步驟所取得之最 或者是最大値，成爲較前述分割鍵更大或者是更小爲 止0 2 ·如申請專利範圍第1項所記載之耦合節點樹之分割 方法’其中，前述最小値或是最大値取得步驟，係爲將前 述處理源頭耦合節點樹之根節點作爲檢索開始節點，在前 述節點對中，僅對構成該節點對之2個的節點中之代表節 點’或考是僅對被配置於與代表節點相鄰接之記憶區域中 的節點作連結，而到達葉節點，藉由此，來求取出前述處 -82- 200834356 理源頭耦合節點樹的索引鍵之最小値或者是最大値之步驟 3·如申請專利範圍第1項又或是第2項所記載之耦合節 點樹之分割方法，其中， 前述耦合節點樹，係被記憶在配列中，前述位置資訊 ，係爲儲存有對應於該位置資訊之節點的前述配列的配列 要素之配列號碼，

   儲存有前述檢索開始節點之配列要素的配列號碼，以 及從前述檢索開始節點起直到到達前述葉節點爲止之儲存 有連結目標之節點的配列要素之配列號碼，係爲被依序保 存在堆疊中者， 前述產生步驟，係爲包含有以下步驟者： 將在前述處理源頭最小値或是最大値取得步驟中所求 取之最小値或是最大値，作爲前述處理目標耦合節點樹之 插入鍵而設定， 實行前述之取得處理目標耦合節點樹的索引鍵之最大 値或是最小値的處理目標最大値或是最小値取得步驟， 對前述插入鍵與前述索引鍵之最大値或是最小値之間 進行位元列比較，而求取出成爲相異之位元値的前端之位 元位置， 藉由該位元位置與被儲存於前述堆疊中之配列號碼的 分支節點之辨別位元位置間的相對位置關係，來決定身爲 包含有保持前述插入鍵之葉節點的節點對之插入位置的處 理目標母節點， -83- 200834356 將該處理目標母節點之前述位置資訊，設爲包含有保 持前述插入鍵之葉節點的節點對之代表節點所被儲存之配 列要素的配列號碼。 4·如申請專利範圍第3項所記載之耦合節點樹之分割 方法，其中，

   前述產生步驟，係更進而具備有：將前述處理目標母 節點，作爲將包含有插入鍵之葉節點插入後之已完成插入 節點而設定之步驟， 前述處理目標最大値或是最小値取得步驟，係爲將前 述已完成插入節點作爲檢索開始節點，而取得前述處理目 標耦合節點樹之索引鍵的最大値或是最小値者。 5.如申請+專利範圍第4項所記載之耦合節點樹之分割 方法，其中，前述削除步驟，係包含有以下步驟： 將把藉由前述處理源頭最小値或是最大値取得步驟所 求取出之最小値或是最大値作爲索引鍵而包含的葉節點， 作爲前述處理源頭耦合節點樹之削除節點而設定， 將與前述削除節點構成同一節點對之節點的內容，寫 入至該當節點對之連結源頭的分支節點中， 將該當節點對削除。 6.—種耦合節點樹之結合方法，係使用有耦合節點樹 (coupled node tree)，該耦合節點樹，係爲由根節點（ro〇t node)、與被配置於相鄰接之記憶區域中的分支節點 (branch node)與葉節點（leaf node)、又或是分支節點彼此 又或是葉節點彼此之節點對所成的使用於位元列檢索之樹 -84- 200834356 (tree)，前述根節點，係爲表示樹之起點的節點，當該樹 之節點係爲1個時，係身爲前述葉節點，而當該樹之節點 係爲2個以上時，則係爲前述分支節點，前述分支節點， 係包含有表示進行位元列檢索之檢索鍵的辨別位元位置、 以及身爲連接（link)目標之節點對的其中一方之節點的代 表節點之位置之位置資訊，前述葉節點，係包含有由檢索 對象之位元列所成的索引鍵（index key)，

   該耦合節點樹之結合方法，係爲將2個的耦合節點樹 作結合之結合方法，並如下述一般地被構成： 將前述樹之任意的節點作爲檢索開始節點，在前述分 支節點中，因應於被包含在該分支節點中之辨別位元位置 之檢索鍵的位元値，而對連結目標之節點對的代表節點或 者是被配置於與其相鄰接之記憶區域中的節點作連結，並 依序反覆進行此，直到到達前述葉節點爲止，藉由此，將 被儲存於前述葉節點中之索引鍵，作爲身爲在將前述檢索 開始節點作爲根節點之前述樹的任意之部分樹的前述檢索 鍵所致之檢索結果的檢索結果鍵， 其特徵爲，具備有以下步驟： 處理源頭最小値或最大値取得步驟，係求取出前述2 個的耦合節點樹之其中一方的處理源頭耦合節點樹之索引 鍵的最小値或者是最大値；和 插入步驟，係在前述2個的耦合節點樹之另外一方的 處理目標耦合節點樹中，插入前述最小値或者是前述最大 値之索引鍵；和 -85- 200834356 削除步驟，係從前述處理源頭耦合節點樹中，將前述 最小値或者是前述最大値之索引鍵削除， 將削除了前述最小値或者是前述最大値之索引鍵的前 述處理源頭耦合節點樹，作爲新的處理源頭耦合節點樹之 前述處理源頭最小値或是最大値取得步驟、前述插入步驟 、以及前述削除步驟，反覆進行此些，直到將前述處理源 頭耦合節點樹全部削除爲止。

   7·如申請專利範圍第6項所記載之耦合節點樹之結合 方法，其中， 前述耦合節點樹，係被記憶在配列中，前述位置資訊 ，係爲對應於該位置資訊之節點所被儲存之前述配列的配 列要素之配列號碼， 儲存有前述檢索開始節點之配列要素的配列號碼，以 及從前述檢索開始節點起直到到達前述前述葉節點爲止之 連結目標的節點所被儲存之配列要素之配列號碼，係依序 被保持在堆疊中， 前述插入步驟，係爲包含有以下步驟者： 將前述最小値或是前述最大値，作爲前述處理目標耦 合節點樹之插入鍵而設定， 實行取得前述處理目標耦合節點樹的索引鍵之最大値 或是最小値的處理目標最大値或是最小値取得步驟， 對前述插入鍵與前述索引鍵之最大値或是最小値之間 進行位元列比較，而求取出成爲相異之位元値的前端之位 元位置， -86- 200834356 藉由該位元位置與被儲存於前述堆疊中之配列號碼的 分支節點之辨別位元位置間的相對位置關係，來決定身爲 包含有保持前述插入鍵之葉節點的節點對之插入位置的母 節點， 將該母節點之前述位置資訊，設爲包含有保持前述插 入鍵之葉節點的節點對之代表節點所被儲存之配列要素的 配列號碼。

   8 ·如申請專利範圍第7項所記載之耦合節點樹之結合 方法，其中，前述削除步驟，係包含有以下步驟： 將把藉由前述處理源頭最小値或是最大値取得步驟所 求取出之最小値或是最大値作爲索引鍵而包含的葉節點， 作爲前述處理源頭耦合節點樹之削除節點而設定， 將與前述削除節點構成同一節點對之節點的內容，寫 入至該當節點對之連結源頭的分支節點中， 將該當節點對削除。 9 · 一種耦合節點樹之分割方法，係使用有耦合節點樹 (coupled node tree)，該耦合節點樹，係爲由根節點（root node)、與被配置於相鄰接之記憶區域中的分支節點 (branch node)與葉節點（leaf node)、又或是分支節點彼此 又或是葉節點彼此之節點對所成的使用於位元列檢索之樹 (tree)，前述根節點，係爲表示樹之起點的節點，當該樹 之節點係爲1個時，係身爲前述葉節點，而當該樹之節點 係爲2個以上時，則係爲前述分支節點，前述分支節點， 係包含有表示進行位元列檢索之檢索鍵的辨別位元位置、 -87- 200834356 以及身爲連接（link)目標之節點對的其中一方之節點的代 表節點之位置之位置資訊，前述葉節點，係包含有由檢索 對象之位元列所成的索引鍵（index key)，

   該分割方法，係爲將前述耦合節點樹之任意的節點作 爲檢索開始節點，在前述分支節點中，因應於被包含在該 分支節點中之辨別位元位置之撿索鍵的位元値，而對連結 目標之節點對的代表節點或者是被配置於與其相鄰接之記 憶區域中的節點作連結，並依序反覆進行此，直到到達前 述葉節點爲止，藉由此，將被儲存於前述葉節點中之索引 鍵，作爲身爲在將前述檢索開始節點作爲根節點之前述耦 合樹的任意之部分樹的前述檢索鍵所致之檢索結果的檢索 結果鍵， 其特徵爲，包含有以下步驟： 取得將身爲分割對象之處理源頭耦合節點樹作分割的 分割鍵之步驟；和 在身爲前述處理源頭耦合節點樹之部分樹，且將前述 分割鍵作爲其之最大値或是最小値者之中，取得身爲最大 之部分樹的根節點之分割節點的分割節點取得步驟·，和 藉由將身爲以前述分割節點爲根節點之部分樹的分割 節點樹插入’而產生新的處理目標之耦合節點樹的產生步 驟；和 將前述分割節點樹從前述處理源頭耦合節點樹削除之 削除步驟。 1 〇·如申請專利範圍第9項所記載之耦合節點樹之分割 -88- 200834356 方法，其中，

   前述分割節點取得步驟，係將前述處理源頭之根節點 作爲前述檢索開始節點，並將前述分割鍵作爲前述檢索鍵 ，而進行檢索，並將身爲從前述根節點起直到前述分割鍵 爲止之檢索中的連結路徑上之分支節點，而在從該分支節 點出發之所有的連結目標處的節點中，均並不存在包含有 較前述分割鍵爲更大或是更小之索引鍵的葉節點，且係爲 在稱合節點樹上之最爲上位的分支節點，作爲前述分割節 點而取得。 11.如申請專利範圍第10項所記載之耦合節點樹之分 割方法，其中，係具備有： 下一分割節點取得步驟，其係將身爲和從前述根節點 起直到前述分割節點爲止之前述連結路徑上的分支節點一 同形成前述節點對之節點，而在耦合節點樹上之較該節點 更爲下位的所有葉節點中，均不包含有較前述分割鍵爲更 大或是更小的索引鍵，且爲耦合節點樹上之最爲上位的節 點’作爲下一個分割節點而取得， 將前述分割節點，作爲前述之下一個分割節點，並實 行前述產生步驟與前述削除步驟。 12·如申請專利範圍第10項又或是第項所記載之耦 合節點樹之分割方法，其中， 前述耦合節點樹，係被記憶於配列中，前述位置資訊 ’係爲儲存有對應於該位置資訊的節點之前述配列的配列 要素之配列號碼， -89- 200834356 儲存有前述檢索開始節點之配列要素的配列號碼’以 及儲存有從前述檢索開始節點起而到達前述葉節點爲止之 連結目標的節點之配列要素的配列號碼，係依序被保持在 堆疊中。 1 3 .如申請專利範圍第1 2項所記載之耦合節點樹之分 割方法，其中，

   前述分割節點取得步驟，係將被儲存在前述堆疊中之 配列號碼依序讀出，直到其成爲儲存有前述代表節點之配 列要素的配列號碼爲止，或是直到其成爲儲存有與前述代 表節點成對之節點的配列要素之配列號碼爲止，將在該讀 出之儲存有前述代表節點之配列要素的配列號碼或是在儲 存有與前述代表節點成對之節點的配列要素之配列號碼中 所儲存之節點，作爲前述分割節點而取得。 1 4.如申請專利範圍第1 3項所記載之耦合節點樹之分 割方法，其中， 前述下一分割節點取得步驟，係將被儲存在前述堆疊 中之儲存於較儲存有前述分割節點之配列要素的配列號碼 爲更前方之配列號碼依序讀出，直到其成爲儲存有與前述 代表節點成對之節點的配列要素之配列號碼爲止，或是直 到其成爲儲存有前述代表節點的配列要素之配列號碼爲止 ’將與在該讀出之儲存有與前述代表節點成對之節點的配 列要素之配列號碼或是儲存有前述代表節點的配列要素之 配列號碼中所儲存之節點成對之節點，作爲前述下一分割 節點而取得。 -90- 200834356

   1 5 · —種耦合節點樹之結合方法，係使用有耦合節點 樹（coupled node tree)，該耦合節點樹，係爲由根節點 (root node)、與被配置於相鄰接之記憶區域中的分支節點 (branch node)與葉節點（leaf node)、又或是分支節點彼此 又或是葉節點彼此之節點對所成的使用於位元列檢索之樹 (tree)，前述根節點，係爲表示樹之起點的節點，當該樹 之節點係爲1個時，係身爲前述葉節點，而當該樹之節點 係爲2個以上時’則係爲前述分支節點，前述分支節點， 係包含有表示進行位元列檢索之檢索鍵的辨別位元位置、 以及身爲連接（link)目標之節點對的其中一方之節點的代 表節點之位置之位置資訊，前述葉節點，係包含有由檢索 封象之位兀列所成的索引鍵（index key)， 該耦合節點樹之結合方法，係爲將2個的耦合節點樹 作結合之結合方法，並如下述一般地被構成： 將前述樹之任意的節點作爲檢索開始節點，在前述分 支節點中，因應於被包含在該分支節點中之辨別位元位置 之檢索鍵的位元値，而對連結目標之節點對的代表節點或 者是被配置於與其相鄰接之記憶區域中的節點作連結，並 依序反覆進行此，直到到達前述葉節點爲止，藉由此，將 被儲存於前述葉節點中之索引鍵，作爲身爲在將前述檢索 開始卽點作爲根節點之前述樹的任意之部分樹的前述檢索 鍵所致之檢索結果的檢索結果鍵， 其特徵爲，具備有以下步驟： 處理源頭最大値或是最小値取得步驟，係求取出前述 -91- 200834356 2個的耦合節點樹之其中一方的處理源頭耦合節點樹之索 引鍵的最大値或者是最小値；和 處理目標最小値或最大値取得步驟，係求取出前述2 個的耦合節點樹之另外一方的處理目標耦合節點樹之索引 鍵的最小値或者是最大値；和

   差分位元位置取得步驟，係求取出··以前述處理源頭 最大値或最小値取得步驟所取得之處理源頭耦合節點樹的 索引鍵之最大値或是最小値，和以前述處理目標最小値或 最大値取得步驟所取得之處理目標耦合節點樹的索引鍵之 最小値或是最大値，其兩者之間的差分位元位置；和 分割結合節點取得步驟，係根據藉由前述差分位元位 置取得步驟所求取之差分位元位置，而求取出身爲從前述 處理源頭所分割並與處理目標結合之部分樹的根節點之分 割結合節點；和 結合位置取得步驟，係求取出根據藉由前述差分位元 位置取得步驟所求取之差分位元位置而將藉由分割結合結 點取得步驟所求得之分割結合節點相結合之處理目標的結 合位置；和 插入步驟，係將藉由前述分割結合節點取得步驟所求 得之分割結合節點，插入至藉由前述結合位置取得步驟所 求得之處理目標的結合位置中；和 削除步驟，係將藉由前述分割結合節點取得步驟所求 得之分割結合節點，從前述處理源頭耦合節點樹中削除。 16·如申請專利範圍第15項所記載之耦合節點樹之結 -92- 200834356 合方法，其中， 前述處理源頭最大値或是最小値取得步驟，係爲將前 述處理源頭耦合節點樹之根節點作爲檢索開始節點，在前 述節點對中，僅對構成該節點對之2個的節點中之代表節 點，或者是僅對被配置於與代表節點相鄰接之記憶區域中 的節點作連結，而到達葉節點，藉由此，來求取出前述處 理源頭耦合節點樹的索引鍵之最大値或者是最小値之步驟 τ 前述處理目標最小値或是最大値取得步驟，係爲將前 述處理目標耦合節點樹之根節點作爲檢索開始節點，在前 述節點對中，僅對構成該節點對之2個的節點中之代表節 點，或者是僅對被配置於與代表節點相鄰接之記憶區域中 的節點作連結，而到達葉節點，藉由此，來求取出前述處 理目標耦合節點樹的索引鍵之最小値或者是最大値之步驟

   1 7 ·如申請專利範圍第1 6項所記載之耦合節點樹之結 合方法，其中， 前述處理源頭耦合節點樹以及前述處理目標耦合節點 樹’係被記憶於配列中，前述位置資訊，係爲儲存有對應 於該位置資訊的節點之前述配列的配列要素之配列號碼， 儲存有在前述處理源頭最大値或是最小値取得步驟中 以及在前述處理目標最小値或是最大値取得步驟中之前述 檢索開始節點之配列要素的配列號碼，以及儲存有從前述 檢索開始節點起而到達前述葉節點爲止之連結目標的節點 -93- 200834356 之配列要素的配列號碼，係依序分別被保持在處理源頭之 堆疊與處理目標之堆疊中。 1 8 ·如申請專利範圍第1 7項所記載之耦合節點樹之結 合方法，其中，

   前述分割結合節點取得步驟，係從儲存在前述儲存於 處理源頭之堆疊中的配列號碼之前一個處的配列號碼中， 來讀取出儲存在該配列號碼之配列要素中的分支節點之辨 別位元位置，直到其成爲較前述差分位元位置爲更上位爲 止，並將在該讀取出之配列要素之後而儲存於前述處理源 頭之堆疊中的配列號碼之配列要素中所儲存之節點，作爲 分割結合節點而求取， 前述結合位置取得步驟，係從儲存在前述儲存於處理 目標堆疊中之配列號碼的前一個處之配列號碼中，來讀取 出儲存在該配列號碼之配列要素中的分支節點之辨別位元 位置，直到其成爲較前述差分位元位置爲更上位爲止，並 將在該讀取出之配列要素之後而儲存於前述處理源頭之堆 疊中的配列號碼之配列要素中所儲存之節點，作爲結合位 置而求取， 1 9 . 一種電腦可讀取之記錄媒體，其特徵爲：係爲記 錄有用以使電腦實行如申請專利範圍第1〜1 8項中之任一 項所記載的耦合節點樹之分割方法或是耦合節點樹之結合 方法的程式。 -94-