推 linhomeyeu:推薦 這篇實用 02/09 12:35
有人回了…（淚）
其實不只是相片，任何需要做排序（或著說允許排序）的資料結構，
大致上都會有這一道需要解的題目。
但老實說，要構成這個題目是有門檻的 - 也就是所謂規模和壓力，
在一定的網站規模和覆載壓力下，這道題目才有檢討的意義。
如果講相片排序會覺得規模較小的話，可以考慮看看以下的情境，
．一個每日有一萬人瀏覽的網站
．網站的管理後台提供了一個檔案管理的系統，在全覽模式下，
可分頁瀏覽和排序所有的 PDF 電子書檔案和 DOC 文件檔。
．網站上已有 5000 筆不分類的 PDF + 5000 筆不分類的 DOC
．網站後台同時提供給 30 個協作團體一起維護，
每個團體每天都會上傳至少 10 個檔案。
在這種條件下可能會比較有真實感一點… XD
※ 引述《tomin (藍藍紫黃橘 粉灰白綠咖)》之銘言：
: 這問題算滿常見的，應該已經有最佳解了吧？
: 我沒寫過，但未來有機會遇到，也想知道答案。
: 不過在還不知道答案的情況下，就來推敲推敲吧！
以小弟有見過的排序用資料庫結構大概就幾種，
一般排序（就是前篇講到的 order 1 2 3 4 5），
表記排序（專門開一個 table 的欄位來儲存排序），例如
user-id order-target order-content
------------------------------------
1 pdf-file 1,3,7,9,44,2,3
表示使用者編號為 1 的 pdf 檔案共有 7 筆，
7 筆資料的 pk 依序為 1,3,7,9,44,2,3
表記法乍看之下好像很好用，但其實很多地方會撞壁（不很實用）
: 目前常見的相簿，都有相簿放多個照片，一本相簿可放照片數上限約為200張。
: 比較少像檔案總管那種無上限的，如果有，應該是不能自訂排序的，
: 亦即頂多只能依檔名、上傳/修改時間、大小、擁有者等方式排序。
: 在此我們假設每次要處理的量limit最多200筆。
: （原po說1000筆，這種情形看能不能取消自訂，變成可改檔名再依檔名排序，
: 或是多增加一些「容器」，如tag、頁碼，減少每次要讀取、更新的照片總數）
: "photo" table 應該要有個欄位叫album，使得每一張相片可對應至一本相簿。
: a.移動單筆時
bingo，不過我在前篇中有說明，自由排序（任意拖曳）的方式暫不討論，
因為那個在各類情況下的演算法會有點複雜，更遑論要追求最佳演算…
所以這邊還是以較基礎的操作為主，以下先列簡單的 DB table：
id order
---------
x 1
y 2
z 3
此處的 SQL 都先以一般排序法來說：
．讀取列表（分頁） SQL 數量 1，異動筆數 0
SELECT `id` FROM `Files` ORDER BY `order` ASC LIMIT 0, 100
．將單筆資料 y 向前移動一位 SQL 數量 2，異動筆數 2
UPDATE `Files` SET `order`=`order`-1 WHERE `id`='y'
UPDATE `Files` SET `order`=`order`+1 WHERE `id`='x'
．將單筆資料 x 往後移動一位 SQL 數量 2，異動筆數 2
UPDATE `Files` SET `order`=`order`+1 WHERE `id`='x'
UPDATE `Files` SET `order`=`order`-1 WHERE `id`='y'
．將單筆資料 z 移到第一位 SQL 數量 2，異動筆數 1 + 2
UPDATE `Files` SET `order`='1' WHERE `id`='z'
UPDATE `Files` SET `order`=`order`+1 WHERE `order`>='1' AND `order`<'3'
AND `id`<>'z'
．將單筆資料 x 移到最後一位 SQL 數量 2，異動筆數 1 + 2
UPDATE `Files` SET `order`='3' WHERE `id`='x'
UPDATE `Files` SET `order`=`order`-1 WHERE `order`<='3' AND `order`>'1'
AND `id`<>'x'
．將單筆資料刪除 SQL 數量 2 ，異動筆數 1 + 2
DELETE FROM `Files` WHERE `id`='x'
UPDATE `Files` SET `order`=`order`-1 WHERE `order`>1
上面這邊列出一般常見可排序資料的操作，
有興趣的可以算算看用夾擊法和表記法所消耗的 SQL 數量、異動筆數
: 我猜測原po描述的情況可能是一個列表，有「上下頂底」按鈕，按了之後可以把
: 目標往上下頂底移動，而不是像臉書相簿可滑鼠拖拉至任意位置。後者感覺比較
: 靈活，如果前者有個功能可將目標換至指定的第xx位置，那兩者才會比較相似。
: 假設從頭到尾只處理一個動作，由於使用者瀏覽時，系統已經把該有的資料都撈
: 出來了，而我們用ajax可以知道使用者要把id編號1對調到2，我會這樣做：
: ajax： exchange_photo?from=1&to=2
: 後端： "update table set pos = 1 where pos = 2 limit 1;"
: +"update table set pos = 2 where pos = 1 limit 1;"
: (同一個db connection內，一次執行兩個update指令)
其實重點不在於 connection，而是在於 DB SQL 的數量（當然建連線也耗時沒錯）
畢竟連線只要不刻意 free 掉，同一隻 php 是可以從頭用到尾的，
另外在寫 code 時，小弟一般都是不信任前端，
不僅僅是為了 injection，同時也是避免暴露過多的 URL 變數操作，
所以鮮少會用到像前端指定移動位置這種…
: b.移動多筆時
: 我偏好等使用者動作都完畢後，再一次處理。使用者可以隨他高興的拖拖拉拉
: 上上下下調整照片、拼拼圖、打字，等到他按下「確定」或是離開頁面前，再
首先多筆移動 / 單筆移動在我們一般的概念下，是各自有各自的一片天 XD
單筆移動的介面溝通次數為 1，
user click -> data sort & save
多筆移動的介面溝通次數至少為 3，
enable free sort mode -> drag & sort -> submit to save
其實也沒有哪個好哪個不好，大多因地制宜而用，
: 把最後的結果儲存起來。如此一來，http request數、db connection次數都
: 可以儘可能的低，即使sql指令可能會很長、很多。我是覺得控制前者數量比
: 較重要，sql指令下得好的話，一個指令才耗時0.000x秒，很多個也沒差。
您可以提看看什麼情況下 connection 會不易控制，說不定是我沒搞清楚…
但一般來說有幾種常見的設計模式都有利於處理 connection
這已經完全可以另開一篇來討論了 XDD
這邊您點到了另一個重點，也就是一開始所提到的「門檻」，
以小弟的經驗，在覆載較大的系統上，往往最需要避免的都是 SQL 的數量，
一道 SQL 命令永遠比兩道好，兩道 SQL 能處理的永遠比 10 道好，
再來則是從結構上考慮，怎麼樣的結構可以以最少的異動量，達到相同的目的，
這邊如果要深入探討會變成討論到資料庫系統本身對於 SQL 的處理流程了，
小弟以簡單的實例來稍微點到就好：
如果今天同時有 10 個人在同一秒開啟 A 頁面，
同一秒向 DB 要求各自不同的 10 項排序（LIMIT 0, 10 ～ LIMIT 90, 10）
而且在同一時刻有 10 個人要開啟 B 頁面，
假設資料庫主機內有 30 個資料表，但這台主機的記憶體超小，
每次只足夠把一個資料表載入記憶體當中，
（也就是說，我們先模擬一個不友善的環境）
那麼此時若是同一秒內送出 10 筆排序 A 頁面資料的 SQL，
而這三種 SQL（排序 A，選取 A，選取 B）交叉送進了 DB 系統，會發生什麼事呢？
以下 UA 代表排序（更新）A（Update A）
SA 代表選取 A （Select A）
SB 代表選取 B （Select B）
順序上若是 UA > SB > SA > UA > SB > SA …這樣的話，
代表資料庫在遇到 UA 時，會
．從索引找一次資料表內的紀錄位置（主鍵有索引）
．更新資料表內容
．更新索引檔內容
如果用 0.001 秒來執行了，接下來遇到 SB
．先找記憶體內有沒有符合的 table cache
．沒有符合，開啟 table B 照排序拉出一份暫存資料表到記憶體中
．拿索引（如果有的話）或直接做比對來篩選出要的資料
再來系統遇到 SA，做的跟遇到 SB 是相同的事，
因為記憶體內目前 cache 的 table B 的暫存表，
所以還是要老實乖乖進去重拉一次 table A 排序暫存表到記憶體內，
（此處僅粗略描述，實際上 DB 的處理還有很多細節的部份 orz）
假設以上每項都要花費 0.001 秒，
那麼最後一道進入的 SQL 至少要等 0.001 x 29，也就是 0.029 秒，
這樣看起來好像不太多，但如果以您以下提的例子，
在這環境下一口氣塞 200 個 SQL 進去，那就很可怕了，
但是如果我們能簡化 SQL 數量，將 10 個 UPDATE 別種演算法替換成 1 道 SQL，
能節省下來的成本就多非常多，因為在同一次的更新（查表）內，
只需將 table 載入記憶體一次，所以實際上時間花費的提昇可能只從
0.001 變成 0.003，但達成的任務卻是同樣的。
: 最穩的作法是重新存所有照片順序，也就是不管只變動1張照片、200張照片全
: 亂掉或反轉順序，我都傳送200張的順序並儲存。
: 理論上有個作法叫linked list，photo table要有頭、尾兩個欄位，我只要傳
: 送(所有有被變動的照片的頭、尾)+(被牽連到的上家的尾、下家的頭)……呃，
: 有可能會搞得很複雜。再者，db似乎無法排序此資料結構，只能捉出來後再用
: 程式排。
是的，這種排序法就像表記排序一樣，在 SELECT 下會拼命撞牆 XD
: 其他作法我還想不到……整個頁面快照、快取？排序好的資料存成某種結構，
: json, tree？非關連式db的作法？雲端運算？XDDD
順道一提，其實 SQL 下的 CASE WHEN 很好用，經常可以拿來整併 SQL，
像是
．將單筆資料 x 往後移動一位 SQL 數量 1，異動筆數 2
UPDATE `Files` SET `order` CASE `id`
WHEN 'x' THEN `order`+1
WHEN 'y' THEN `order`-1 END
WHERE `id` IN ('x','y')
不過還是沒有夾擊法強悍就是… orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.205.80