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