給定兩張表，每張表中的每一條資料包含相同長度的項。如表（1）所示，每一條資料包含四個項，編號為T1的資料的項的內容為A, B, C, D，每條資料的項的內容按照字典序排序。如果表（1）中的一條資料與表（2）中的一條資料的前k-1項相同，最后一項不同，（假定兩張表中沒有一條資料具有完全相同的項），則這兩條資料可以連接為一條新的具有k+1項的資料，例如表（1）中的T1和表（2）中的T1，前3項相同，最后一項不同，可以連接得到一條新的資料A, B, C, D, E, 將兩張表進行全連接，可以得到一個每個項都是5的表，例如，連接表（1）和表（2）可以得到表（3）。
表（1）示例資料
ID 項
T1 A, B, C, D
T2 A, B, E, F
T3 A, C, E, F
T4 B, C, D, E
…
表（2）示例資料
ID 項
T1 A, B, C, E
T2 A, B, D, F
T3 A, C, E, K
T4 A, C, D, E
…
表（3）連接后的表
ID 項
T1 A, B, C, D, E
T2 A, C, E, F, K
…
在傳統的表連接操作中，需要耗費的時間復雜度為O(n2)。
要求：設計演算法，降低該連接操作的復雜度，提高效率。
uj5u.com熱心網友回復：
項是什么？4個欄位還是1個欄位內容用逗號分隔？uj5u.com熱心網友回復：
是一個欄位的內容uj5u.com熱心網友回復：
既然是資料庫，應該還是考察的如何讓索引生效吧，只要索引生效就可以把復雜度降低到O(n)。可以考慮分別截取前3個項和最后一個項，建立聯合索引。然后用explain看一下掃描行數
uj5u.com熱心網友回復：
如果不考慮索引，而是將問題轉化為合并兩個順序表并洗掉重復元素，有什么比較好的方法呢？uj5u.com熱心網友回復：
一樣的，直接合并也得先找出前三項相同的資料，躲不開連接。只要做連接驅動表的O(n)就少不了，優化就要想辦法避免遍歷被驅動表變成O(n2)，所以核心還是讓索引生效
連接后再洗掉重復項只會更慢
uj5u.com熱心網友回復：
我之前對這個題目的理解就是先根據ID對這兩個表進行連接，連接完后對項進行合并，我這個理解應該是錯的，請問大佬能細談你的整體思路嗎?uj5u.com熱心網友回復：
方便再解釋一下這個n平方的復雜度是如何產生的嗎？uj5u.com熱心網友回復：
想象表1表2是兩個文本檔案，如果讓你手工做這個匹配，你怎么做。先取出表1第一條，去第二個表里找前三項一樣的，如果不用搜索，那么就是把表2的資料從頭看一遍，這個復雜度是n。表1資料挨個取也是n次，全部查完就是n x n。
然后你發現可以用搜索，就是取第一條的 A, B, C 去表2里直接搜，找到后再看第4項是否匹配，這個操作按大O表示法是O(1)，忽略。表1資料挨個取完查完復雜度是n。
資料庫除去各種優化，連接的基本原理跟這個思路是一樣的。
uj5u.com熱心網友回復：
嗯好的，理解了。大佬，請問還有不占用額外空間或占用較少額外空間的方法嗎？uj5u.com熱心網友回復：
不額外占用空間就是重建表2，截取前三項設定為一個欄位并且設為主鍵，第4項作為第二個欄位uj5u.com熱心網友回復：
請問表1需要進行處理嗎?
uj5u.com熱心網友回復：
表1不需要處理uj5u.com熱心網友回復：
大佬，可以詳細講一下這個方法嗎?
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/13401.html
標籤：MySQL
上一篇：來自初學者的問題，感謝指教！
下一篇：使用logstash-input-mongodb同步資料，報錯：ArgumentError:invalid byte sequence in UTF-8