對b+樹的並行操作的製作方法

2023-10-17 06:54:14 3

對b+樹的並行操作的製作方法
【專利摘要】描述用於B+樹的並行處理的技術和系統的實施例。具有劃分和再分配的並行B+樹處理模塊可包括並行地對B+樹運行B+樹操作批命令的線程集合。操作批命令可在線程之間來劃分。隨後，可執行搜索，以確定B+樹中的哪些葉節點將要受到哪些操作影響。然後，線程可在相互之間再分配操作，使得多個線程將不會對同一葉節點進行操作。然後，線程可並行地對B+樹的葉節點執行B+樹操作。對B+中的節點的後續修改可與沿樹向上工作的線程相似地再分配和並行執行。
【專利說明】對B+樹的並行操作
【技術領域】
[0001 ] 本申請涉及數據處理的【技術領域】，更具體來說，涉及與對B+樹並行地執行B+樹操作關聯的方法和設備。
【背景技術】
[0002]除非本文另加說明，否則本小節中所述的資料不是本申請中的權利要求的現有技術，並且不是通過包含在本小節中而承認是現有技術。
[0003]隨著對高吞吐量資料庫的需求符合移動計算、雲計算以及許多臺式應用的蓬勃發展，資料庫越來越多地用於現代計算系統中。這些影響力迅速推動作為關鍵伺服器應用的資料庫系統的使用、大小和重要性。
[0004]在許多資料庫中，B+樹可用作資料庫中的索引。例如，B+樹可包含許多關鍵字(key)，其中的每個指向資料庫中的一組記錄。B+樹提供對所存儲值的有效檢索，特別是在具有大量記錄的系統中。但是，用於從B+樹來檢索值並且用於修改樹的現有技術不可有效地利用現代並行處理技術和/或能力。
[0005]資料庫索引中的B+樹的並行處理的一種常見方式可使用單獨運行的線程，每個線程異步地處理單個查詢。但是，異步技術可要求用於修改操作的鎖存器(例如對存儲器中資源的控制，以防止線程訪問相同數據)。另外，異步技術可呈現對檢索操作的變化需要。例如，一些異步技術可將不同的鎖存器類用於檢索和修改操作，而其它異步技術可以不限制檢索操作。在兩種情況下，許多這類方法可因鎖存器的使用而遭受性能損失，從而降低對B+樹的並行處理的利用。
【專利附圖】

【附圖說明】
[0006]將通過附圖所示的非限制性的示範實施例來描述本發明的實施例，附圖中相似的參考標號表示相似的元件，附圖包括:
圖1是示出按照本公開的多種實施例、對B+樹執行B+樹操作的批命令或者序列的示例多線程B+樹操作模塊的框圖；
圖2是示出按照本公開的多種實施例的多線程B+樹處理模塊的框圖；
圖3示出按照多種實施例的示例多線程B+樹操作過程；
圖4示出按照多種實施例的示例多線程B+樹操作劃分過程；
圖5示出按照多種實施例的示例多線程B+樹並行操作過程；
圖6示出按照多種實施例的示例多線程B+樹並行操作有效再分配過程；
圖7a和圖7b是示出按照多種實施例、在線程之間的B+樹操作的有效再分配的一示例的框圖；
圖8示出按照多種實施例的另一示例多線程B+樹並行操作執行過程；
圖9示出按照多種實施例的示例多線程B+樹並行節點修改過程；
圖10示出按照多種實施例的示例多線程B+樹並行節點修改有效再分配過程； 圖11示出按照多種實施例的示例多線程B+樹根操控過程；以及 圖12示出按照多種實施例的示例計算環境。
【具體實施方式】
[0007]本文中公開與並行B+樹操作關聯的方法、設備和存儲介質。在多種實施例中，一種方法可包括由至少多個線程(其由一個或多個處理器核來操作)來識別將要對B+樹執行的有序操作序列的多個操作的工作集合(work set)。操作的工作集合是逐個集合無關的(set-wise independent),並且可由線程並行地對B+樹的葉節點逐個集合分別執行。工作集合可對應地由線程並行地識別。另外，該方法還可包括由對應數量的線程並行地對B+樹的葉節點來執行多個操作的工作集合。此外，該方法可包括由至少多個線程來修改B+樹的內部節點，以考慮對B+樹的葉節點執行的操作的效果。
[0008]在多種實施例中，識別可包括由控制任務來劃分有序操作序列，以生成分別與線程關聯的有序操作的多個初始子集。在備選實施例中，識別可包括由多個線程從有序操作序列中分別選擇有序操作不同的一個或多個來劃分有序操作序列，以生成分別與線程關聯的有序操作的多個初始子集。
[0009]在多種實施例中，識別還可包括由線程在初始集合之間有效地再分配初始集合的有序操作，以便有效地識別逐個集合無關的操作的工作集合。此外，有效再分配以有效地進行識別可包括由線程中的相應線程分別使用操作的相應初始集合來搜索B+樹，以便分別識別和生成葉節點的多個初始集合，以供線程分別對其執行操作。另外，有效再分配以有效地進行識別可包括由線程中的相應線程通過分別選擇葉節點的多個初始集合的對應集合中的葉節點，至少部分基於葉節點的初始集合，來分別生成多個葉節點的工作集合。線程可具有對應線程標識符(其經過排序)，以及由特定線程從對應初始集合中選擇的葉節點可以是不在與具有比相應線程的線程標識符要低的線程標識符的線程對應的任何初始集合中的葉節點。逐個集合無關的操作的工作集合可以是與葉節點的工作集合對應關聯的有序操作序列的子集。
[0010]在多種實施例中，該方法可包括同步線程，並且在所有線程分別完成了搜索並且葉節點的初始集合均已生成之後，開始葉節點的工作集合的相應生成。在多種實施例中，執行可包括由線程並行地執行相應操作的工作集合的操作。此外，由線程執行對應操作的工作集合的操作可包括由線程按順序執行對應操作的工作集合的操作。另外，執行還可包括由線程分別將操作的工作集合的檢索操作的檢索的值記錄在線程的對應檢索緩衝器中。該方法還可包括執行檢索緩衝器中存儲的檢索的值的併集，以形成有序操作序列的檢索回答集。
[0011]在多種實施例中，修改可包括由線程對於根節點之下的所有樹層的所有內部節點，每次一個樹層來連續修改B+樹的內部節點。此後，根節點可由線程之一或者控制任務來修改。在多種實施例中，修改就在葉節點之上的樹層的內部節點可包括由線程並行地識別修改操作的多個初始集合(其需要對就在葉節點之上的樹層的內部節點進行)，以考慮對B+樹的葉節點執行的操作的效果。此外，修改可包括在修改操作的初始集合之間有效地再分配修改操作的初始集合的修改操作，以便有效地識別將要由線程並行地對就在葉節點之上的樹層的內部節點執行的多個修改操作的工作集合。另外，修改可包括由線程並行地對就在葉節點之上的樹層的內部節點執行相應工作集合修改操作。
[0012]在多種實施例中，修改特定樹層的內部節點可包括由線程並行地識別修改操作的多個初始集合(其需要對特定樹層的內部節點進行)，以考慮對緊接著的較低樹層的內部節點執行的修改操作的效果。此外，修改特定樹層的內部節點可包括在修改操作的初始集合之間有效地再分配修改操作的初始集合的修改操作，以便有效地識別將要由線程並行地對特定樹層的內部節點執行的多個修改操作的工作集合。另外，修改特定樹層的內部節點可包括由線程並行地對特定樹層的內部節點執行相應工作集合修改操作。
[0013]在整個實施例中，由線程修改任何樹層的特定內部節點還可包括:在由線程對特定內部節點執行修改操作之後，響應所修改的特定內部節點超過對內部節點能夠保持的元素數量的上限，而由線程將特定內部節點分為兩個或更多內部節點，或者響應所修改的特定內部節點下降到低於對內部節點必須保持的元素數量的下限，而由線程去除特定內部節點。
[0014]在多種實施例中，其中有序操作序列可包括檢索與關鍵字關聯的一個或多個數據元素的一個或多個檢索操作、將一個或多個數據元素附加到與關鍵字關聯的數據結構的插入操作、或者從與關鍵字關聯的數據結構中去除一個或多個數據元素的刪除操作。在多種實施例中，線程的至少兩個可由一個或多個處理器核中的不同處理器核來運行。
[0015]在多種實施例中，可配備一種設備，以實施本文所述方法的一個或多個。在多種實施例中，該設備可包括計算機可讀存儲器或存儲裝置，其配置成存儲B+樹。該設備可包括耦合到存儲器的處理器布置，處理器布置包括一個或多個處理核。該設備可包括多個並行樹操作模塊，其配置成由處理器布置來操作以分別執行本文所述的各種方法，該設備還可包括控制模塊，其配置成由處理器布置來操作以執行本文所述的各種方法。在多種實施例中，一個或多個非暫時計算機可讀介質可包括指令，其響應由計算裝置的執行而使計算裝置執行本文所述的各種方法的一個或多個操作。
[0016]在多種實施例中，一種方法可包括由計算機裝置來劃分將要對B+樹執行的有序操作序列，以生成有序操作的多個初始子集。該方法還可包括由計算機裝置產生多個並行B+樹操作線程。該方法還可包括由計算機裝置向多個並行B+樹操作線程的每個來指配有序操作的相應初始子集。所產生的並行B+樹操作線程可配置成識別將要對B+樹執行的有序操作序列的多個操作的工作集合。操作的工作集合可以是逐個集合無關的。操作的工作集合還可由線程並行地對B+樹的葉節點逐個集合分別執行。操作的工作集合還可對應地由線程並行地識別。所產生的並行B+樹操作線程還可配置成對B+樹的葉節點並行地執行多個操作的工作集合，並且修改B+樹的內部節點，以考慮對B+樹的葉節點執行的操作的效果O
[0017]將使用本領域的技術人員通常用於向本領域的其他技術人員傳達其工作主旨的術語來描述說明性實施例的多種方面。然而，本領域的技術人員將清楚地知道，僅通過所述方面的一部分也可實施備選實施例。為了便於說明，提出具體數量、材料和配置，以便提供對說明性實施例的透徹了解。但是，本領域的技術人員將清楚地知道，即使沒有具體細節也可實施備選實施例。在其它情況下，省略或簡化了眾所周知的特徵，以免影響對說明性實施例的理解。
[0018]此外，各種操作將按照最有助於了解說明性實施例的方式依次描述為多個分立操作；但是，描述的順序不應當被理解為意味著這些操作一定是順序相關的。具體來說，這些操作不需要按照提出的順序來執行。
[0019]本文中使用詞語「有效地」和短語「有效地再分配」。操作可通過執行另一個操作來「有效地」執行，而沒有實際執行該操作。例如，在本描述中，各種操作在通過線程分別修改葉節點的集合(線程將要對其分別執行操作)，在線程之間「有效地再分配」。通過分別修改/再分配葉節點的集合，在線程之間「有效地再分配」操作。
[0020]如本文在描述操作集合中所使用的短語「逐個集合無關的」表示如下事實:集合中的操作與該集合外部的任何其它操作沒有相關性。例如，操作集合可具有多個操作(其對相同關鍵字值進行操作)，以及這些操作因此對於使總執行結果是正確的，在操作上是彼此順序相關的。例如，接著對關鍵字k的插入操作之後對關鍵字k的檢索操作必然對先前插入操作是執行順序相關的，或者檢索結果可能沒有產生預計結果。如果操作集合A與操作集合B被說成是「逐個集合無關的」，則操作之間的這種執行順序相關性在集合A與B的操作之間可以不存在。在多種實施例中，如本文所使用的術語「集合」的使用不可被理解為必然暗示「集合」的任何數學定義的要求。具體來說，本文所述的操作集合可包括例如根據關鍵字或者根據時間經過排序的操作。另外，本文所述的操作集合可包括單個關鍵字的多個操作。
[0021]如本文所使用的術語「線程」一般表示指令的單元或者(一個或多個)單元的(一個或多個)實例，其可經過調度以用於在計算裝置上進行並行處理。所使用的術語預計包括所有形式的並行處理單元並且與其是同義的，非限制性地例如執行線程、過程、光纖、SMD通道等。
[0022]反覆使用短語「在一個實施例中」或者「在實施例中」。該短語一般並不表示同一個實施例；但它也可表示同一個實施例。術語「包含」、「具有」和「包括」是同義詞，除非上下文另加說明。短語「A/B」表示「A或B」。短語「A和/或B」表示「㈧、(B)或者(A和B) 」。短語「A、B和C中的至少一個」表示「 (A)、(B)、(C)、(A和B)、(A和C)、(B和C)或者(A、B和 C) 」。
[0023]現在參照圖1，圖1是示出按照本公開的實施例、對示例B+樹105執行一個或多個有序B+樹操作的批命令或序列210 (其是基於關鍵字的)的多線程B+樹處理模塊200的框圖。如下面將更詳細描述，多線程B+樹處理模塊200可配置成基本上並行地執行有序操作210，由一個或多個處理器核來操作。
[0024]具體來說，在多種實施例中，B+樹處理模塊200的各種執行線程(以下簡單地稱作線程)可配置成識別有序操作的批命令或序列210的多個操作的工作集合。操作的工作集合是逐個集合無關的，並且因此可由線程並行地對B+樹105的葉節點逐個集合分別執行。此外，工作集合可對應地由線程並行地識別。另外，線程可配置成並行地對B+樹105的葉節點執行所識別的工作集合操作。此後，線程可修改B+樹105的內部節點，以考慮對B+樹105的葉節點執行的操作的效果。
[0025]如圖1所示，B+樹105可包括多個內部節點、例如根節點100。內部節點可包括指向其它內部節點和/或葉節點、例如葉節點110、120、130的指針。在多種實施例中，B+樹可包括某種類型的B村，其中使用葉節點來存儲或指向所有數據。為了便於了解，B+樹中的節點可說成是位於各種樹層，其中根節點位於最高樹層(例如第O層)，根節點的子位於下一個或者緊接著的較低樹層(例如第I層)，根節點的孫子位於另一個緊接著的較低級(例如第2層)等。B+樹105的葉節點可共同說成是位於樹的最低樹層。雖然圖1的示例B+樹105僅包含兩個樹層，但是本公開可對僅受例如存儲器、存儲裝置、處理器核的數量和速度等的計算資源所限制的任何數量的樹層的B+樹來實施。
[0026]在多種實施例中，各種數據可根據關鍵字來索引。關鍵字可用於從B+樹105來搜索和檢索數據。因此，如所示，示例葉節點Iio可包含關鍵字I和2，其分別指向數據dl和d2。類似地，示例葉節點120可包含關鍵字3和4，其分別指向數據d3和d4，以及示例葉節點130可包含關鍵字5、6和7，其分別指向數據d5、d6和d7。另外，如所示，示例根節點100可包括分別指向葉節點110、120和130的指針115、125和135。在操作期間，新關鍵字可連同關聯數據一起插入B+樹105，和/或現有關鍵字可從B+樹105中刪除。
[0027]在多種實施例中，指針結合位於內部節點中的關鍵字可促進B+樹操作的執行。內部節點中的關鍵字可對於特定指針來指示哪些關鍵字可通過跟隨該指針來找到。因此，指針115指向葉節點110，其包含3以下的關鍵字；指針125指向葉節點120，其包含值3或以上但5以下的關鍵字；以及指針135指向葉節點130，其包含值5或以上的關鍵字。
[0028]在多種實施例中，當諸如插入、檢索和刪除(以下所述)之類的B+樹操作將要相對特定關鍵字、對樹來執行時，可使用這些指針。檢索操作可檢索與關鍵字關聯的一個或多個數據元素。插入操作可將一個或多個數據元素附加到與關鍵字關聯的數據結構。刪除操作可從與關鍵字關聯的數據結構中去除一個或多個數據元素，或者去除與關鍵字關聯的所有數據元素。樹的內部節點中的關鍵字和指針可用來沿樹由上至下進行搜索，直至找到包含正確關鍵字的葉節點。在找到正確關鍵字之後，可執行操作。操作可引起在葉節點中添加或刪除關鍵字。這可引起B+樹105中的節點的修改，如以下所述。
[0029]在多種實施例中，B+樹105中的節點的程度(例如，任一個節點可指向的子節點或關鍵字的數量)可受到限制。這些限制可與樹「階數(order)」相關聯。例如，如果B+樹105具有階數4，則各內部節點的程度可限制到2與4個子之間，以及每個葉節點的程度可限制到2與3個關鍵字之間。這些限制可在對B+樹105執行操作之後，例如通過對B+樹105的節點執行修改來保持。
[0030]在多種實施例中，在創建過多子時，例如在將關鍵字插入B+樹105時，B+樹105可超過其上限程度。當那種情況發生時，可執行修改，以將節點分為附加節點。其中創建附加節點的這種修改可提高原始節點的父的程度。這時，這又可要求對節點的父執行一個或多個進一步修改，例如分割父節點。這種分割可沿B+樹105從葉節點朝根節點向上繼續進行。
[0031]類似地，在多種實施例中，如果從節點中刪除關鍵字，則該節點可下降到低於其下限程度。當那種情況發生時，可執行一個或多個修改，以刪除該節點。由於被刪除節點可剩餘關鍵字(或者子)，所以可對節點的父執行進一步修改，以將剩餘關鍵字(或者子)加入節點的父。進一步修改則可對樹的高層來執行(例如，如果父這時已經超過其上限程度，則分割節點的父)。
[0032]在多種實施例中，在對B+樹105的節點執行操作和/或修改時，對樹的較高樹層處的節點可要求進一步修改。這些修改可沿B+樹105向上傳播，直到對B+樹的根節點執行修改，如本文所述。[0033]在具體實現中，按照多種實施例所使用的B+樹可對資料庫的列進行索引。對於資料庫D，B+樹105可使用來自總序集K和存儲對(k，r；)的關鍵字來對資料庫的列進行索引，其中rk*是引用輔助結構rk (其列舉資料庫D中採用關鍵字k所引用的元組的標識符(或者「ID」))的指針。繼續這個語法，又可經由至少三種類型的操作，相對關鍵字k，來對資料庫Td的B+樹105進行操作，如先前所公開。第一操作可以是檢索(TD，k)操作，其在被執行時返回rk或者空集合{}(若k不在Td中的話)。第二操作可以是操作插入(TD，(k,e))。當k在Td中時，插入的執行將值e附加到rk。否則，可將新的rk= {e}添加到D，以及可將關鍵字-指針對(k，O添加到TD。第三操作可以是刪除(TD，(k, e))操作。當k在Td中時，刪除的執行可從rk中去除e，以及如果rk的元組大小|rk|=0，則可從Td中去除(k，r:)。否則，如果k不在Td中，則可執行空操作。
[0034]圖2是更詳細示出按照本公開的多種實施例的多線程B+樹處理模塊200的框圖。如所示，在多種實施例中，多線程B+樹處理模塊200可對B+樹220執行有序B+樹操作的批命令或序列210 ;例如，B+樹可表示資料庫的一部分。B+樹220可保持在包含多線程B+樹處理模塊200的計算裝置的存儲器中；在其它實施例中，B+樹220而是可存儲在存儲器外部，例如存儲在計算裝置的存儲裝置上。在多種實施例中，有序B+樹操作的批命令或序列210可包括以上所述的多個檢索、插入和刪除操作。
[0035]在多種實施例中，多線程B+樹處理模塊200可包括控制模塊245，其作為控制線程240運行。控制線程240可配置成將有序B+樹操作的批命令或序列210劃分為B+樹操作的多個初始較小集合。控制線程240還可產生各種B+樹並行操作線程250，如以下所述。在備選實施例中，一個或多個B+樹並行操作線程250可在初始化時預先產生，並且可等待到它們使B+樹操作執行才開始執行。在多種實施例中，B+樹並行操作線程250可作為樹操作模塊255的多個實例的不同執行來產生。在多種實施例中，B+樹並行操作線程250可按照與樹操作模塊實例255的1:1對應性來產生。
[0036]在產生B+樹並行操作線程250之後，B+樹操作的劃分集合則可分別由B+樹並行操作線程250來顯式指配(或者與其隱式關聯)和使用，以便分別對B+樹220執行有序B+樹操作的批命令或序列210中的對應操作。為了便於描述，B+樹並行操作線程250在本文中可單數地簡單稱作「線程250」或者統稱為「線程250」。
[0037]通過將樹操作模塊255的不同實例作為獨立線程250來操作(如本文所述受到限制)，並行B+樹處理模塊200可提供對B+樹250的有序B+樹操作的批命令或序列210的有效並行處理。在多種實施例中，線程250可提供有標稱排序。在實施例中，線程的順序可以不影響線程250的執行的任何順序。排序而是可由線程用來確定哪些操作可由哪些線程來執行，以便促進線程之間的操作的有效再分配，以實現操作的逐個集合無關性，以及促進並行操作，如以下所述。在多種實施例中，不同線程可工作於各種計算機處理器和/或核布置。例如，在多種實施例中，不同線程可工作於處理器的同一核、單個處理器的不同核和/或不同計算機處理器的不同核。
[0038]在多種實施例中，可在運行時為線程250的每個顯式指配B+樹操作的工作集合260(其是那個線程250特定的)或者隱式地與其關聯。在多種實施例中，各線程250的所指配/關聯B+樹操作的工作集合260可從B+樹操作的批命令或序列210的初始劃分子集來得出或識別。工作集合是逐個集合無關的，從而使它們能夠並行地執行。換言之，工作集合中的操作與工作集合外部的任何其它操作沒有相關性。線程250可首先分別對B+樹220的葉節點並行地執行樹操作的所指配/關聯工作集合260。各線程250可保持或者確保其工作集合中的操作260的順序。
[0039]此後，線程250可修改B+樹220的內部節點，以考慮對葉節點執行的樹操作的效果。在多種實施例中，線程250可每次一個樹層地連續修改內部節點，從就在葉節點之上的樹層開始，並且朝根節點移動。在多種實施例中，對每層的內部節點的修改操作265也可有效地組成為逐個集合無關的工作集合，並且由線程並行地執行。
[0040]雖然為了便於了解而僅對線程I示出樹操作260和節點修改265的工作集合，但是應當理解，可為各線程250指配/關聯B+樹操作的工作集合260和節點修改的工作集合265。在多種實施例中，當節點修改沿B+樹220從就在葉節點之上的樹層處的內部節點朝根節點向上移動時，各線程可與其它線程有效地再分配節點修改，以便提供工作集合之間的逐個集合無關性，以實現它們的並行執行。
[0041]在多種實施例中，線程250還可分別分配有檢索緩衝器268，以用於存儲檢索操作的結果。在B+樹操作210完成時，線程250或者控制線程240其中之一可執行檢索緩衝器268中存儲的所有所檢索數據的併集，以生成對B+樹220的B+樹操作210的檢索輸出。在多種實施例中，可在高速緩存或者系統存儲器中或者在大容量存儲裝置中分配按線程檢索緩衝器268。
[0042]圖3示出按照多種實施例的示例多線程B+樹操作過程300。在多種實施例中，過程300的一個或多個操作可被重排序、 去除或者分為進一步操作。在多種實施例中，該過程可相對B+樹、例如B+樹220來執行。該過程可在操作320開始，其中可接收有序B+樹操作的批命令或序列、例如有序B+樹操作的批命令或序列210。
[0043]隨後，在操作330，有序操作可劃分為初始按線程集合(例如Ρι、ρ2、".ρη)，從其中，稍後可得出逐個集合無關的工作集合260。隨後，在操作335，控制線程240可產生用於B+樹操作的按線程集合的並行執行的一個或多個並行B+樹操作線程250。
[0044]隨後，在操作340，線程250的每個可並行地從初始劃分集合來得出它們相應逐個集合無關的工作集合。在多種實施例中，線程具有線程標識符(例如tpt2、…^)，並且根據線程標識符來排序。線程\可通過首先識別由初始劃分集合Pi中的操作對其操作的葉節點，但是排除也被具有較低線程階的其它線程(例如h、…丨㈠、tg)所識別的葉節點，來得出其逐個集合無關的工作集合。線程\的操作的逐個集合無關的工作集合是與剩餘葉節點關聯的那些操作。將與所排除葉節點關聯的操作有效地再分配給其它線程。在實現中，可以或者可以不實際創建工作集合。在多種實施例中，初始標識可由線程並行地執行。然後，線程可在並行地檢查所識別葉節點的任一個是否也被較低線程階的線程所識別並且因此應當被排除之前進行同步。在得出或識別相應逐個集合無關的工作集合時，線程可執行工作集合中的操作，並且對B+樹的葉節點並行地操作。下面還描述操作340的進一步示例。
[0045]最後，在操作350，多線程B+樹處理模塊200可執行各種線程250的檢索緩衝器368中存儲的所檢索結果的併集，並且返回組合結果作為對B+樹操作的檢索操作的檢索結果。因此，該過程則可結束。
[0046]圖4示出按照多種實施例的示例多線程B+樹操作劃分過程400。在多種實施例中，劃分可由作為控制線程240運行的控制模塊245來執行。此外，在多種實施例中，過程400的一個或多個操作可被重排序、去除或者分為進一步操作。該過程可在操作410開始，其中有序B+樹操作的批命令或序列210中的操作可根據關鍵字來分類。在多種實施例中，這種分類可簡化以後的樹操作和節點修改的有效再分配，以實現各種工作集合的逐個集合無關性，如以下所述。在多種實施例中，有序B+樹操作的批命令或序列210中的操作順序可在分類之後基於按關鍵字來保持或者確保。因此，甚至在操作410之後，將要對給定關鍵字k執行的每個B+樹操作也仍然可按照它們在有序B+樹操作的批命令或序列210中原來的相同相對順序。B+樹操作的原始按關鍵字順序的這種保持對以下操作是有用的:確保結果與當批命令中的各操作按照其原始順序來執行時所預計的結果一致。
[0047]隨後，在操作420，批命令或序列210中的B+樹操作可初始分為劃分子集(例如Ρι>Ρ2> ".Ρη)。在多種實施例中，η為整數，並且等於將要用於並行操作的線程的預計數量。在多種實施例中，劃分可由控制線程240來執行。在一些備選實施例中，而是線程250本身可例如通過從批命令210選擇預定數量的B+樹操作(例如，最初為線程提供近似相等數量的操作的預定數量)，來執行初始劃分。在多種實施例中，在整個劃分中，B+樹操作可至少基於按關鍵字來保持順序。B+樹操作的原始按關鍵字順序的這種保持再次可用於確保結果與當批命令中的各操作按照其原始順序來執行時所預計的結果一致。然後，該過程可結束。
[0048]圖5示出按照多種實施例的示例多線程B+樹並行操作過程500。在多種實施例中，過程500可由線程250、樹操作模塊255的運行實例來執行。在多種實施例中，過程500的一個或多個操作可被重排序、去除或者分為進一步操作。在多種實施例中，過程500的操作可由多個線程250並行地執行。通過並行操作，在多種實施例中，線程可執行B+樹操作的批命令210中的全體B+樹操作。
[0049]該過程可在操作510開始，其中線程250(\)可識別它負責的葉節點的排他集合。線程250 Ui)可從B+樹操作的所指配/關聯初始劃分集合(Pi) 260中搜索B+樹220的葉節點(Li)(其保持與操作對應的關鍵字)的初始集合。`在多種實施例中，操作510可包括由線程250(\)對操作的所指配/關聯初始劃分(Pi)集合中指示的每個關鍵字的迭代搜索。在多種實施例中，操作510的搜索可迭代地並且無需參照順序來執行，因為任何搜索結果反映分派操作批命令時的樹的狀態，因為對B+樹220尚未發生修改。在多種實施例中，線程250(\)在執行搜索之後，可等待其它運行線程完成其搜索(圖5中稱作「同步」)。在多種實施例中，這種同步可允許線程250(其並行操作)在繼續其它操作之前全部處於同一階段。
[0050]隨後，在操作520，線程250 (t,)可通過操作的有效再分配，來得出其逐個集合無關的工作集合(Wsi)。如先前所述，在線程250 Ui)已經得到葉節點(Li)的初始集合之後，線程250(\)可排除也被具有較低線程階的其它線程(例如h、…tiftg)所識別的葉節點。線程250 \的逐個集合無關的操作的工作集合(Wsi)是與剩餘葉節點關聯的操作。在多種實施例中，再分配之後沒有保持任何B+樹操作的那些線程250可停止執行(未示出)。下面描述操作520的進一步示例。
[0051]隨後，在操作530，線程250可與其它線程並行地對B+樹執行逐個集合無關的B+樹操作的工作集合中的操作，例如對B+樹執行B+樹操作的相應逐個集合無關的工作集合中的操作。下面描述操作530的進一步示例。[0052]然後，線程250可繼續進行到操作540，其中可執行節點修改。在多種實施例中，這些節點修改可保持在線程的節點修改的集合265中。下面描述操作540的進一步示例。在多種實施例中，線程250在執行節點修改之後，可等待其它運行線程完成其節點修改(圖5中稱作「同步」)。在多種實施例中，這種同步可允許線程250(其並行操作)在繼續其它操作之前全部處於同一階段。
[0053]在判定操作545，線程250可確定它是否對B+樹的根節點進行操作。如果線程對根節點進行操作，則線程可繼續進行到操作560，以操控B+樹的根節點。下面描述操作560的進一步示例。然後，該過程可結束。
[0054]但是，如果線程沒有對根節點進行操作，則線程可繼續進行到操作550，其中線程250可通過線程之間的節點修改的有效再分配來得出節點修改的逐個集合無關的工作集合。隨後，在判定操作555，線程250可在通過再分配得出工作集合之後，確定它是否在節點修改的逐個集合無關的工作集合265中仍然具有節點修改。如果線程250的節點修改的工作集合265這時為空，則該線程可停止執行，並且然後該過程可結束。
[0055]但是，如果線程250在節點修改的工作集合265中確實有剩餘的節點修改，則線程250可繼續進行到操作558，其中該線程則可繼續對B+樹更高一層進行操作。然後，該線程可重複進行操作540以及操作550和555 (若它仍然不在根節點的話)。線程250可繼續這個重複，並且可繼續執行通過有效再分配來得出工作集合以及在B+樹的連續更高層的節點修改，同時它繼續使節點修改在每層執行。如先前所述，在多種實施例中，這種重複可繼續進行到線程250對於給定下一層沒有節點修改或者到達根節點。在多種實施例中，通過過程500的並行操作，各種線程250可對B+樹由下(葉節點)至上(根節點)進行操作，執行操作，並且然後重複修改節點(均並行地進行)，直至到達B+樹的根節點。
[0056]圖6示出按照多種實施例的示例B+樹操作有效再分配過程600。在多種實施例中，B+樹操作有效再分配可由運行樹操作模塊255的實例的線程250來執行。在多種實施例中，過程600的一個或多個操作可被重排序、去除或者分為進一步操作。
[0057]在多種實施例中，通過過`程`600的操作的執行，線程250可基於節點(必須對其進行操作或者修改)有效地再分配給定樹層處的操作。通過這樣做，線程250可確保各節點完全由一個線程來操作或修改，從而防止線程之間的爭用。另外，在多種實施例中，通過基於節點的有效地再分配，過程600可避免對操作的基於低粒度的分配的需要。由於各操作可影響單個節點，所以對線程250的操作的指配或關聯可通過線程確定節點擁有權來暗示。
[0058]在多種實施例中，各線程250 i可確定葉節點的初始集合L/的子集(在這裡稱作L/ )。在一個實施例中，葉節點的子集可通過下式確定:


L:: |λ?: L
在多種實施例中，這可意味著，如果沒有低階線程(例如h、…tiftg)在葉節點的對應初始集合中識別了那個葉節點，則線程250 Ui)可保持葉節點(以及因此保持葉節點的操作)。它可有助於認識到，在多種實施例中，過程600的操作在各線程250已經完成搜索並且已經識別葉節點的初始集合之後來執行，由此允許這個比較得出葉節點的工作集合。
[0059]另外，在多種實施例中，B+樹操作的批命令可在進行劃分和搜索之前，根據關鍵字值來分類，如上所述。因此，在線程250的搜索期間識別的葉節點Li，={1Λ I/,...}也可在樹中由左至右來排序。具體來說，葉節點可在葉節點的各集合中來排序(根據關鍵字)，以及葉節點還可跨線程來排序。
[0060]因此，在操作610，其中線程250(\)可確定葉節點的初始集合中的葉節點是否也被其低階線程250 …tiftg所識別。隨後，在操作620，線程250 Ui)可排除也被其低階線程所識別的葉節點，從而從操作的工作集合中有效地丟棄與所排除節點關聯的那些操作。然後，在操作630，線程250 Ui)可同樣添加來自其它線程250的操作(若那些操作對剩餘葉節點起作用的話)。通過執行操作620和630，線程250可為其自己生成要與其它線程並行執行的逐個集合無關的B+樹操作的工作集合，從而分別對逐個集合無關的操作的工作集合進行工作。然後，該過程可結束。
[0061 ] 在過程600的一些實施例中，線程250各可將其所識別葉節點的集合保持在存儲器(其是其它線程250可訪問的)中。這些實施例可為線程250提供檢查所識別葉節點並且相應地有效再分配操作的能力，而無需節點之間的顯式通信。此外，在多種實施例中，線程250可執行操作的有效丟棄和添加，而無需相互之間的顯式通信。在多種實施例中，這些操作可無需顯式通信來操控，因為各線程250沿用相同過程，並且因為線程沒有開始操作的有效分配，直到所有搜索已經完成。在多種實施例中，在整個有效再分配中，B+樹操作可至少基於按關鍵字來保持順序。B+樹操作的原始按關鍵字順序的這種保持可用於確保結果與預計一致。
[0062]圖7a和圖7b是示出按照多種實施例、在線程之間的B+樹操作的有效再分配的一示例的框圖。圖7a和圖7b示出包含關鍵字(對其將要執行操作)的三個葉節點的兩個集合的示例。在圖7a的示例中，三個線程250已經執行搜索，並且已經識別關鍵字的初始集合(它們對其具有B+樹操作的按線程集合中的B+樹操作)。線程O具有對葉節點710和720中的關鍵字的B+樹操作。線程I具有對葉節點720和730中的關鍵字的B+樹操作。以及線程2具有對葉節點730中的關鍵字的B+樹操作。可以注意到，在所提供的示例中，線程跨葉節點按順序與毗連關鍵字關聯。一些實施例可呈現這個特性，特別是當操作按照關鍵字順序來劃分時。但是，在其它實施例 中，操作可按照不同順序來指配給線程。
[0063]在圖7b的示例中，線程250各執行了過程600，並且相應地有效再分配B+樹操作。因此，線程O保持葉節點710中的關鍵字的B+樹操作，因為它是最低階線程。另外，因為線程O具有對葉節點720中的關鍵字的一個或多個操作，所以它遠離線程I對那個葉節點中的關鍵字進行剩餘操作。類似地，因為線程I具有對葉節點730中的關鍵字的一個或多個操作，所以它遠離線程2對那個葉節點中的關鍵字進行剩餘操作。線程2在這個示例中沒有剩下操作，並且因此過早結束。
[0064]圖8示出按照多種實施例的進一步示例B+樹並行操作執行過程800。在多種實施例中，B+樹操作的執行可由運行樹操作模塊255的實例的線程250來執行。在多種實施例中，過程800的一個或多個操作可被重排序、去除或者分為進一步操作。該過程可在操作810開始，其中線程250的B+樹操作的工作集合260中的B+樹操作的每個可基於按關鍵字來審查，而無需參照其它關鍵字。隨後，在操作820，可從各關鍵字的操作集合中去除冗餘和/或不必要的操作。例如，如果插入操作之後接著刪除而沒有中間檢索，則可安全地去除插入和刪除操作，因為它們將對樹或者對任何結果沒有影響。類似地，如果B+樹操作的工作集合260包括特定關鍵字的連續插入操作而沒有該關鍵字的中間刪除操作，則可去除插入操作的一個或多個。[0065]隨後，在操作830，線程250可對各關鍵字的B+樹操作的工作集合中的操作迭代進行，並且執行B+樹操作。因此，在多種實施例中，以及對於各種關鍵字，線程250可在操作840執行插入操作，其中插入元組，如上所述。此外，如果新關鍵字因插入而將要插入B+樹中，貝1J在這時可記錄插入關鍵字的節點修改。
[0066]在多種實施例中，以及對於各種關鍵字，線程可在操作850執行刪除操作，其中刪除元組，如上所述。此外，如果關鍵字因刪除操作而將要從B+樹中刪除，則在這時也可記錄刪除關鍵字的節點修改。在多種實施例中，以及對於各種關鍵字，線程250可在操作860執行檢索操作，其中結果可基於關鍵字來檢索，並且存儲在檢索緩衝器268中，供線程250以後返回。如先前所述，這些檢索緩衝器的內容稍後可由多線程B+樹處理模塊200來結合和返回，如上所述。在操作870，線程250可繼續對關鍵字的下一個操作迭代進行，以及在關鍵字的各操作完成之後對下一個關鍵字的操作重複進行。然後，該過程可結束。
[0067]可以注意到，B+樹操作可基於按關鍵字來執行，因為對不同關鍵字的B+操作相對資料庫D的狀態相互無關。因此，多線程B+樹處理模塊200可單獨檢查影響各關鍵字的操作。此外，在多種實施例中，對給定關鍵字的所有B+操作綁定到單個葉節點，並且這個葉節點將僅由單個線程250來修改。在多種實施例中，可觀察操作的不同順序。
[0068]圖9示出按照多種實施例的示例B+樹並行節點修改過程900。在多種實施例中，節點修改可由運行樹操作模塊255的實例的線程250來執行。在多種實施例中，過程900的一個或多個操作可被重排序、去除或者分為進一步操作。在多種實施例中，節點修改可對B+樹的各種層來執行，如上所述。因此，節點修改可直接源於對葉節點進行的插入或刪除操作，或者可基於低層修改(其從低層節點向上傳播到特定層處的內部節點)。
[0069]該過程可在操作910開始，其中線程250可按照節點修改的逐個集合無關的工作集合來執行節點修改。隨後，在多種實施例中，操作930、940或950之一可根據對節點程度(例如節點中的元素的數量)的節點修改的結果來執行。
[0070]因此，如果程度在操作930、例如因引起具有過少子的節點的刪除操作而低於下限，則可執行操作933、935和938。在操作933，線程250可記錄將要通過刪除具有過低程度的節點而孤立的任何關鍵字。這些所記錄的孤立關鍵字可在稍後的點又加入B+樹，如以下所述。在操作935，可刪除節點。在操作938，線程250可創建節點修改，以便施加在較高樹層，從而表明已經刪除節點。節點修改可包括新孤立關鍵字的列表。
[0071]類似地，如果經修改節點的程度在操作950、例如因引起具有過多子的節點的插入操作而高於上限，則可執行操作953和955。在操作953，線程250可將經修改節點分為兩個或更多新節點。然後，在操作955，線程250可返回節點修改，以便施加在較高樹層，從而表明已經分割節點。節點修改可包括新創建節點的指示。
[0072]在過高或過低程度的任一種情況下，例如通過在B+樹的較高層重複進行過程900，返回修改則可在該樹的較高層使用。可執行這種重複，以便修改可沿B+樹向上傳播。最後，如果經修改節點的程度在操作940處於上限和下限之內，則在多種實施例中，在樹的那一層，在那個線程中沒有發生進一步節點修改操作。然後，過程900可結束。
[0073]圖10示出按照多種實施例的示例B+樹並行節點修改有效再分配過程1000。在多種實施例中，有效B+樹節點修改再分配可由運行樹操作模塊255的實例的線程250來執行。在多種實施例中，過程1000的一個或多個操作可被重排序、去除或者分為進一步操作。[0074]在多種實施例中，通過過程1000的操作的執行，線程250可基於節點(其必須對給定樹層來修改)有效地再分配給定樹層處的節點修改。通過這樣做，線程250可確保各節點完全由一個線程來修改，從而防止線程之間的爭用。
[0075]在多種實施例中，在樹層d，各線程250 i可從節點的初始集合來確定將要在那一層修改的工作子集(在這裡稱作M/)。在一個實施例中，節點的工作子集可通過下式確定:
【權利要求】
1.一種計算機實現的方法，包括: 由一個或多個處理器核操作的至少多個線程來識別將要對B+樹執行的有序操作序列的多個操作的工作集合，其中: 所述操作的工作集合是逐個集合無關的； 所述操作的工作集合將由所述線程並行地對所述B+樹的葉節點逐個集合分別執行；以及 所述操作的工作集合對應地由所述線程並行地識別；以及 由所述對應的多個線程對所述B+樹的所述葉節點並行地執行所述多個操作的工作集合；以及 由至少 所述多個線程來修改所述B+樹的內部節點，以考慮對所述B+樹的所述葉節點執行的所述操作的效果。
2.如權利要求1所述的方法，其中，識別包括: 由控制任務來劃分所述有序操作序列，以生成分別與所述線程關聯的所述有序操作的多個初始子集；或者 由所述多個線程從所述有序操作序列中分別選擇所述有序操作不同的一個或多個來劃分所述有序操作序列，以生成分別與所述線程關聯的所述有序操作的多個初始子集。
3.如權利要求2所述的方法，其中，識別還包括由所述多個線程在所述多個初始集合之間有效地再分配所述多個初始集合的所述有序操作，以便有效地識別所述多個逐個集合無關的操作的工作集合。
4.如權利要求3所述的方法，其中，有效地再分配以有效地識別包括由所述線程中的相應線程進行以下步驟: 使用操作的所述多個初始集合中的操作的相應初始集合分別搜索所述B+樹，以便分別識別和生成要分別對其執行操作的所述線程的葉節點的多個初始集合；以及 通過分別選擇葉節點的所述多個初始集合的對應集合中的葉節點，至少部分基於葉節點的所述多個初始集合，來分別生成多個葉節點的工作集合； 其中: 所述線程具有經過排序的對應線程標識符； 由特定線程從對應初始集合選擇的所述葉節點是不在與具有比所述相應線程的線程標識符要低的線程標識符的線程對應的任何初始集合中的葉節點；以及 所述逐個集合無關的操作的工作集合是與所述葉節點的工作集合對應關聯的所述有序操作序列的子集。
5.如權利要求4所述的方法，還包括同步所述線程，並且在所有線程分別完成了所述搜索並且葉節點的所述多個初始集合均已生成之後，開始所述多個葉節點的工作集合的相應生成。
6.如權利要求4所述的方法，其中，執行包括由所述線程並行地執行所述相應操作的工作集合的操作。
7.如權利要求6所述的方法，其中，由線程執行對應操作的工作集合的操作包括由所述線程按順序執行所述對應操作的工作集合的操作。
8.如權利要求6所述的方法，其中，執行還包括由所述線程分別將所述多個操作的工作集合的檢索操作的檢索的值記錄在所述線程的對應檢索緩衝器中。
9.如權利要求8所述的方法，還包括執行所述檢索緩衝器中存儲的所述檢索的值的併集，以形成所述有序操作序列的檢索回答集。
10.如權利要求1所述的方法，其中，修改包括: 由所述線程對於根節點之下的所有樹層的所有內部節點，每次一個樹層來連續修改所述B+樹的內部節點；以及 此後由所述線程之一或者控制任務來修改所述根節點。
11.如權利要求10所述的方法，其中，修改就在所述葉節點之上的樹層的內部節點包括: 由所述線程並行地識別需要對就在所述葉節點之上的所述樹層的內部節點進行的修改操作的多個初始集合，以考慮對所述B+樹的葉節點執行的所述操作的效果； 在修改操作的所述初始集合之間有效地再分配修改操作的所述初始集合的修改操作，以便有效地識別將要由所述線程並行地對就在所述葉節點之上的所述樹層的內部節點執行的多個修改操作的工作集合；以及 由所述線程並行地對就在所述葉節點之上的所述樹層的內部節點執行所述相應工作集合修改操作。
12.如權利要求10所述的方法，其中，修改特定樹層的內部節點包括: 由所述線程並行地識別需要對所述特定樹層的內部節點進行的修改操作的多個初始集合，以考慮對所述緊接著的較低樹層的內部節點執行的所述修改操作的效果； 在修改操作的所述初始集合之間有效地再分配修改操作的所述初始集合的修改操作，以便有效地識別將要由所述線程並行地對所述特定樹層的內部節點執行的多個修改操作的工作集合；以及 由所述線程並行地對所述特定樹層的內部節點執行所述相應工作集合修改操作。
13.如權利要求10所述的方法，其中，由線程來修改任何樹層的特定內部節點還包括在由所述線程對所述特定內部節點執行修改操作之後進行以下步驟: 響應所修改的特定內部節點超過對內部節點能夠保持的元素數量的上限,而由所述線程將所述特定內部節點分為兩個或更多內部節點；或者 響應所述修改的特定內部節點下降到低於對內部節點必須保持的元素數量的下限，而由所述線程去除所述特定內部節點。
14.如權利要求1所述的方法，其中，所述有序操作序列包括檢索與關鍵字關聯的一個或多個數據元素的一個或多個檢索操作、將一個或多個數據元素附加到與關鍵字關聯的數據結構的插入操作、或者從與關鍵字關聯的數據結構中去除一個或多個數據元素的刪除操作。
15.如權利要求1所述的方法，其中，所述多個線程中的至少兩個線程由所述一個或多個處理器核中的不同處理器核來運行。
16.—種設備,包括: 計算機可讀存儲器或存儲裝置，配置成存儲B+樹； 耦合到所述存儲器的處理器布置，所述處理器布置包括一個或多個處理核；以及 多個並行樹操作模塊，配置成由所述處理器布置來操作，以便分別進行以下操作:識別將要對所述B+樹執行的有序操作序列的多個操作的工作集合，其中: 所述操作的工作集合是逐個集合無關的； 所述操作的工作集合將由所述並行樹操作模塊並行地對所述B+樹的葉節點逐個集合分別執行；以及 所述操作的工作集合對應地由所述並行樹操作模塊並行地識別；以及由所述對應並行樹操作模塊對所述B+樹的所述葉節點並行地執行所述多個操作的工作集合；以及 由至少所述並行樹操作模塊來修改所述B+樹的內部節點，以考慮對所述B+樹的所述葉節點執行的所述操作的效果。
17.如權利要求16所述的設備，其中，並行樹操作模塊配置成作為識別多個操作的工作集合的一部分以進行以下操作: 使用操作的所述多個初始集合中的操作的相應初始集合分別搜索所述B+樹，以便分別識別和生成要分別對其執行操作的所述並行樹操作模塊的葉節點的多個初始集合；以及通過分別選擇葉節點的所述多個初始集合的對應集合中的葉節點，至少部分基於葉節點的所述多個初始集合，來分別生成多個葉節點的工作集合； 其中: 所述並行樹操作模塊經 過排序； 由特定並行樹操作模塊從對應初始集合中選擇的所述葉節點是不在與具有比所述相應並行樹操作模塊更低階的並行樹操作模塊對應的任何初始集合中的葉節點；以及 所述逐個集合無關的操作的工作集合是與所述葉節點的工作集合對應關聯的所述有序操作序列的子集。
18.如權利要求16所述的設備，其中，所述多個並行樹操作模塊還配置成由所述處理器布置來操作，以便分別: 對於根節點之下的所有樹層的所有內部節點，每次一個樹層來連續修改所述B+樹的內部節點；以及 此後由所述並行樹操作模塊之一或者控制模塊來修改所述根節點。
19.如權利要求18所述的設備，其中，多個並行樹操作模塊配置成作為修改特定樹層的內部節點的一部分以進行以下操作: 並行地識別需要對所述特定樹層的內部節點進行的修改操作的多個初始集合，以考慮對所述緊接著的較低樹層的內部節點執行的所述修改操作的效果；以及 在修改操作的所述初始集合之間有效地再分配修改操作的所述初始集合的修改操作，以便有效地識別將要由所述並行樹操作模塊並行地對所述特定樹層的內部節點執行的多個修改操作的工作集合；以及 並行地對所述特定樹層的內部節點執行所述相應工作集合修改操作。
20.如權利要求16所述的設備，還包括控制模塊，配置成由所述處理器布置來操作，以便劃分有序B+樹操作序列，以生成分別與所述多個並行樹操作模塊關聯的所述有序操作的多個初始子集。
21.如權利要求16所述的設備，其中，所述多個並行樹操作模塊中的至少兩個並行樹操作模塊由所述一個或多個處理器核中的不同處理器核來操作。
22.包括指令的一個或多個非暫時計算機可讀介質，所述指令響應由計算裝置的執行而使所述計算裝置執行包括下列步驟的一個或多個操作: 由至少多個線程來識別將要對B+樹執行的有序操作序列的多個操作的工作集合，其中: 所述操作的工作集合是逐個集合無關的； 所述操作的工作集合將由所述線程並行地對所述B+樹的葉節點逐個集合分別執行；以及 所述操作的工作集合對應地由所述線程並行地識別；以及 由所述對應的多個線程對所述B+樹的所述葉節點並行地執行所述多個操作的工作集合；以及 由至少所述多個線程來修改所述B+樹的內部節點，以考慮對所述B+樹的所述葉節點執行的所述操作的效果。
23.如權利要求22所述的計算機可讀介質，其中，識別包括: 由控制任務來劃分所述有序操作序列，以生成分別與所述線程關聯的所述有序操作的多個初始子集；或者 由所述多個線程從所述有序操作序列中分別選擇所述有序操作不同的一個或多個來劃分所述有序操作序列，以生成分別與所述線程關聯的所述有序操作的多個初始子集。
24.如權利要求22所述的計算機可讀介質，其中，識別還包括由所述多個線程在所述多個初始集合之間有效地再分配所述多個初始集合的所述有序操作，以便有效地識別所述多個逐個集合無關的操作的工作集合。
25.如權利要求24所述的計算機可讀介質，其中，有效地再分配以有效地識別包括由所述線程中的相應線程: 使用操作的所述多個初始集合中的操作的相應初始集合分別搜索所述B+樹，以便分別識別和生成要分別對其執行操作的所述線程的葉節點的多個初始集合；以及 通過分別選擇葉節點的所述多個初始集合的對應集合中的葉節點，至少部分基於葉節點的所述多個初始集合，來分別生成多個葉節點的工作集合； 其中: 所述線程具有經過排序的對應線程標識符； 由特定線程從對應初始集合選擇的所述葉節點是不在與具有比所述相應線程的線程標識符要低的線程標識符的線程對應的任何初始集合中的葉節點；以及 所述逐個集合無關的操作的工作集合是與所述葉節點的工作集合對應關聯的所述有序操作序列的子集。
26.如權利要求22所述的計算機可讀介質，其中，修改包括: 由所述線程對於根節點之下的所有樹層的所有內部節點，每次一個樹層來連續修改所述B+樹的內部節點；以及 此後由所述線程之一或者控制任務來修改所述根節點。
27.如權利要求26所述的計算機可讀介質,其中，修改特定樹層的內部節點包括: 由所述線程並行地識別需要對所述特定樹層的內部節點進行的修改操作的多個初始集合，以考慮對所述緊接著的較低樹層的內部節點執行的所述修改操作的效果；在修改操作的所述初始集合之間有效地再分配修改操作的所述初始集合的修改操作，以便有效地識別將要由所述線程並行地對所述特定樹層的內部節點執行的多個修改操作的工作集合；以及 由所述線程並行地對所述特定樹層的內部節點執行所述相應工作集合修改操作。
28.—種計算機實現的方法，包括: 由計算機裝置來劃分將要對B+樹執行的有序操作序列，以生成所述有序操作的多個初始子集； 由所述計算機裝置來產生多個並行B+樹操作線程； 由所述計算機裝置向所述多個並行B+樹操作線程的每個來指配所述有序操作的相應初始子集； 其中所產生的並行B+樹操作線程配置成: 識別將要對B+樹執行的有序操作序列的多個操作的工作集合，其中: 所述操作的工作集合是逐個集合無關的； 所述操作的工作集合將由所述線程並行地對所述B+樹的葉節點逐個集合分別執行；以及 所述操作的工作集合對應地由所述線程並行地識別；以及 對所述B+樹的所述葉節點並行地執行所述多個操作的工作集合；以及 修改所述B+樹的內部節點，以考`慮對所述B+樹的所述葉節點執行的所述操作的效果。
29.如權利要求28所述的方法，其中，所述所產生並行B+樹操作線程還配置成作為識別的一部分，有效地由所述多個線程在所述多個初始集合之間有效地再分配所述多個初始集合的所述有序操作，以便有效地識別所述多個逐個集合無關的操作的工作集合。
30.如權利要求28所述的方法，還包括將所述並行B+樹操作線程的兩個或更多調度成由所述計算裝置的獨立處理核來運行。
【文檔編號】G06F9/06GK103765381SQ201180073146
【公開日】2014年4月30日 申請日期:2011年8月29日 優先權日:2011年8月29日
【發明者】J.D.塞瓦爾, C.金, J.楚賈尼, N.R.薩蒂什 申請人:英特爾公司