前綴搜索的最佳數據庫查詢

我有一個數據集，它是一個前綴範圍的列表，並且前綴不是全部相同的大小。這裏有幾個例子：前綴搜索的最佳數據庫查詢

low: 54661601 high: 54661679 "bin": a 
low: 526219100 high: 526219199 "bin": b 
low: 4305870404 high: 4305870404 "bin": c

我想查哪個「bin」的對應於具有相應前綴的特定值。例如，值5466160179125211將對應於「bin」a。在重疊的情況下（其中很少），我們可以返回最長的前綴或所有前綴。

最佳算法顯然是某種樹，可以在其中插入bin對象，其中樹的每個連續級別表示越來越多的前綴。

問題是：我們如何在數據庫中實現這個（在一個查詢中）？可以修改/添加數據集。什麼是最好的數據&這個查詢設計？使用mongo或MySQL的答案是最好的。

來源

2012-06-15 Peyton

對於MySQL，您可能必須使用存儲過程，您可以調用該存儲過程將值映射到bin。所述過程將查詢每行的桶列表並且執行算術或字符串操作來查找匹配的桶。您可以通過使用固定長度的前綴來改進此設計，這些前綴排列在固定數量的圖層中。你可以爲你的樹分配一個固定的深度，每一層都有一個表格。採用這兩種方法之一，你都不會得到樹狀表現。

如果你想做更復雜的事情，我懷疑你必須使用不同的平臺。

SQL Server有一個層次的數據類型： http://technet.microsoft.com/en-us/library/bb677173.aspx

PostgreSQL有一個CIDR數據類型。我不熟悉它的查詢支持級別，但理論上你可以在你的db內部建立一個路由表，並用它來分配桶： http://www.postgresql.org/docs/7.4/static/datatype-net-types.html#DATATYPE-CIDR

來源

2012-06-15 16:22:37

「Optimal」對不同的人意味着不同的事情。看起來你可以做一些事情，比如將你的低值和高值保存爲varchars。然後，所有你需要做的就是

select bin from datatable where '5466160179125211' between low and high

或者，如果你有一些理由將值作爲整數表中，你可以做在查詢中鑄造。

我不知道這是否會給你一個巨大的數據集可怕的表現。我希望我明白你想要做什麼。

來源

2012-06-15 17:04:40 Chud

Peyton！ :)

如果需要把一切都爲整數，並希望它有一個單一的查詢工作，這應該工作：

select bin from datatable where 5466160179125211 between 
     low*pow(10, floor(log10(5466160179125211))-floor(log10(low))) 
    and ((high+1)*pow(10, floor(log10(5466160179125211))-floor(log10(high)))-1);

在這種情況下，它將在數54661601億之間搜索（最低低位前綴&的號碼與要查找的號碼位數相同）和546616799999999（最高位號碼前綴高的前綴&與查找號碼位數相同）。在高位前綴比低位前綴多的情況下，這仍然可以工作。它也應該工作（我認爲）在數字短於前綴長度的情況下，前面的解決方案中的varchar代碼可能會給出不正確的結果。

您將要進行實驗，以比較其在查詢大量的內聯數學（如本解決方案）對使用VARCHAR處理的性能表現。

編輯：性能似乎是真的好或者甚至在沒有索引的大表的方式;如果您可以使用varchars，那麼您可以通過索引低和高列來進一步提高性能。請注意，如果任何前綴具有初始值爲零，那麼一定要使用varchars。這裏有一個補丁，允許地方使用VARCHAR處理時的數量比前綴短的情況：

select * from datatable2 where '5466' between low and high 
    and length('5466') >= length(high);

來源

2012-06-15 19:40:54 Jamie

如果您對在您的前綴範圍重疊數溫和的假設，就可以做你最好使用MongoDB或MySQL。在下面的答案中，我將用MongoDB進行說明，但它應該很容易將此答案移植到MySQL。

首先，讓我們改一下這個問題了一下。當你談論匹配「前綴範圍」，我相信你實際上是在談論一個字典排序下找到正確的範圍（憑直覺，這只是字符串的自然字母排序）。例如，其前綴與54661601至54661679相匹配的一組數字恰好是以字符串形式按字典順序大於或等於「54661601」，但按字典順序小於「54661680」的數字集。因此，您應該做的第一件事是將1加到您的所有高範圍內，以便您可以用這種方式表達您的查詢。在蒙戈，你的文件看起來是這樣的

{low: "54661601", high: "54661680", bin: "a"} 
{low: "526219100", high: "526219200", bin: "b"} 
{low: "4305870404", high: "4305870405", bin: "c"}

現在的問題就變成了：給定一組的形式[低，高）的一維區間，我們如何能夠快速找到其間隔（ s）包含一個給定的點？要做到這一點最簡單的方法是在任的低或高領域的指標。我們使用高位字段。在mongo shell中：

db.coll.ensureIndex({high : 1})

現在讓我們假設間隔根本不重疊。如果是這種情況，則對於給定查詢點「x」，唯一可能的包含「x」的區間是具有大於「x」的最小值的那個區間。因此，我們可以查詢該文件並檢查其低值是否也小於「x」。舉例來說，這將打印出匹配的間隔，如果有的話：

現在

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
     function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
)

假設而不是假設間隔完全不重疊的，你認爲每一個間隔少於ķ重疊鄰近的間隔（我不知道k會對你有什麼價值，但希望它是小的）。在這種情況下，只需更換1 ķ在上面的「限制」，即

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
     function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
)

這是什麼算法的運行時間？索引使用B樹存儲，因此，如果有Ñ間隔在數據集，它需要爲O（log Ñ）時間由高值，則O（ķ來查找第一匹配文檔）時間遍歷下一個文件，總共爲0（log n + k）time。如果ķ是恆定的，或實際上任何小於爲O（log Ñ），那麼這是漸近最優（這是在計算的標準模型;我不計算外部存儲器傳輸數或任何幻想）。

這種情況下發生的唯一情況是，當k很大時，例如，如果某個較大的間隔包含幾乎所有其他間隔。在這種情況下，運行時間爲O（Ñ）。如果您的數據是這樣構建的，那麼您可能會想要使用不同的方法。一種方法是使用蒙戈的「2D」的索引，你低和高值編纂X和ÿ座標。然後你的查詢會對應查詢在X的給定區域點 - Ÿ平面。這在實踐中可能會表現得很好，儘管目前實現了2d索引，但最壞的情況仍然是O（n）。

對於所有k的值，都有許多理論結果達到了O（log n）性能。他們按照優先搜索樹，段樹，間隔樹等名稱進行搜索。但是，這些是專用數據結構，您必須自行實施。據我所知，目前沒有流行的數據庫實現它們。

來源

2012-06-16 20:09:26 matulef

前綴搜索的最佳數據庫查詢

回答

相關問題