※ 引述《reader (讀者)》之銘言： : 標題: Re: [心得] 資料存取 : 時間: Thu Mar 10 03:39:04 2005 : : 推 ledia:請問粗估的複雜度大概是怎麼算的呢? 140.112.30.55 03/10 嗯，目前的實作，細節不論，大致就是 1 對 16 的樹狀結構。 假設完全平均分佈，那麼總共 m 維 n 項的資料，一個維度的資料數是 n / m, 樹狀結構深度是 ceil(log16(n / m)). 全部樹狀結構深度則會 是 m * ceil(log16(n / m)) [A], 但完全平均是不可能的。若是各維度 註標分佈極為平均，反而結果會是 ceil(log16(n)) + m - 1 [B], 單在 第一個維度就分散掉所有節點，後面各維度只會有一個節點。 由於大多數時候 [A] > [B], 所以用 [A] 式做比較基準。 而有 n 項資料的樹狀結構半滿的狀態會是 ceil(log16(n * 2)) [C] 結合 [A] 跟 [C] 就成了 m * ceil(log16(n / m * 2)) [D] 但我們其實不是那麼清楚樹狀結構會填得多滿，所以正確來說應該是： m * ceil(log16(n / m * k)) [D'] (k 未知) 由於 m, k >= 1, m 通常小於 16, 而 k 最大為 16, 兩者數字範圍 相近，而 k 通常會是在 1 ~ 3 之間較為常見, m 也以 2 為最常見。 於是在簡化式子時可互消，於是成為 m * ceil(log16(n)) [E] 而 m 若大於 16, [E] > [D'], 所以仍是高估的式子。 顯然 [E] 式是一個較簡化的偏高估計，所以用此式當做粗估值，但 或許用 m * log16(n) [E'] 更佳，可減去一些偏高的估計。 * 在實作細節上，由於 1:16 的樹狀結構，空間使用的成長太劇烈， 一般資料庫的 B+ tree 也只是 1:5 或 1:7, 所以會採兩階段式的 變動，先建 4 個子節點空間，遇到衝突再擴增為 16 個節點空間。 不過這就是程式技巧而已了。 -- 註1：知道 B+ tree 的話，應該有助於理解這裡在講什麼 註2：其實 1:16 的 tree depth 是 log17(n) 才對... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.222.173.26