我想了解哪些在here描述simipiled緩存忘卻先行陣列，並從35頁this presentation緩存無視先行陣列
分析插入成簡體 分形樹：
- 合併成本2個大小爲X的數組的成本爲O（X = B）塊I/O。合併是非常有效的I/O 。
- 合併的每個元素的成本爲O（1/B），因爲O（X）元素合併爲 。
- 每個元素被合併的最大次數是O（logN）。
- 平均插入成本是O（logN個/ B）
我可以understhand＃1，＃2和＃3，但我不理解＃4，從紙，合併可以被認爲是作爲二進制加法進位，例如（31）B可以被提供：當插入新項目（加1）時，應該有5 = log（32）合併（5進位）。但是，在這種情況下，我們必須合併32個元素！另外，如果每次我們加1，那麼從0到2^k將執行多少次carryies？ anwser應該是2^k - 1。換句話說，每插入一個合併！
so＃4是如何計算的？
儘管在最壞情況下合併元素（以及傳輸）的數量爲N，並且合併總數也是同一訂單，但插入成本的平均值仍爲對數。它來自兩個事實：合併成本不同，低成本合併的數量遠高於高成本合併的數量。
通過示例可能會更容易看到。我們設置B = 1（即每塊1個元素，每個合併具有代價的最壞情況）和N = 32（例如，我們將32個元素插入到最初的空陣列中）。
一半插入（16）將元素放入大小爲1的空子數組中，因此不會導致合併。剩餘的插入中，一個（最後一個）需要合併（移動）32個元素，一個（第16個）移動16個，兩個（第8個和第24個）移動8個元素，4個移動4個元素和8個移動2個元素。因此，元素移動的總數爲96，每次插入平均移動3次。
希望有所幫助。
一般而言，每增量變化比特的分攤數量爲2 = O（1）。
這是邏輯/推理的證明。 http://www.cs.princeton.edu/courses/archive/spr11/cos423/Lectures/Binary%20Counting.pdf
這是一個通過實驗的「證明」。 http://codepad.org/0gWKC3rW
您的代碼實際上證明每插入一次合併 – Chang 2011-05-23 05:25:17
第一個日誌B級適合（單頁）內存，所以在這些級別發生的任何事情都不會產生I/O。 （這也解決了rrenaud分析中存在的問題，即每插入一個O（1）合併，因爲您只在第一個日誌B合併後開始支付）。踢。
從元素的角度考慮工作。它會合並O（log N）次。它每次發生時都會收取O（1/B）。它的總插入成本是O（（log N）/ B）（需要額外的元素來區分O（log N/B），這將是非常不好的插入性能 - 甚至比B樹更差）。
「平均」成本實際上是攤銷成本 - 這是您對該元素插入的金額。更正式地說，它是插入N個元素，然後除以N的全部工作。O（（log N）/ B）的分攤成本實際上意味着插入N個元素爲O（（N log N）/ B）I/Os - 用於整個序列。這與B樹相比是非常有利的，對於N個插入總共進行O（（N log N）/ log B）個I/O。除以B顯然比分爲B好很多。
您可能會抱怨說這項工作非常笨拙，您有時會進行一次插入操作，導致大量級聯合並。沒關係。您不會收取所有合併到最後一次插入。由於（logN）/ B通常遠低於1，所以每個人在爲所參與的每次合併付出少量費用。由於所有合併過程中每個人的收費方式都低於單個I/O參與
如果您不喜歡攤銷分析，並且您認爲即使插入吞吐量增加了幾個數量級，您會發生什麼情況？當單次插入可能導致工作量巨大？啊哈！有一些標準的方法可以對這種數據結構進行分解，在每次插入過程中，您都可以進行一些搶先合併。你會得到相同的I/O複雜性（你必須聽取我的意見），但對於那些關注分期分析和取消結果的人來說，這是非常標準的東西。
完全披露：我是COLA論文的作者之一。另外，rrenaud在我的算法類。另外，我是Tokutek的創始人。
你如何將32個有序列表與5個有序列表合併成一個線性區域？即使使用分數級聯（http://zh.wikipedia.org/wiki/Fractional_cascading），它仍然是O（N）。 – Chang 2011-05-23 02:43:34
在這篇論文中，有人說：「cache-oblivious lookahead array ...由log2（N）數組或級別組成......第k個數組的大小爲2k，數組連續存儲在內存中。」而且，他們的成本模型僅計算磁盤到內存的傳輸。 – 2011-05-23 04:54:29