※ 引述《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