存儲/檢索數據結構

我已經在Python中實現了一個後綴樹以進行全文搜索，並且它工作得很好。但是有一個問題：索引文本可能非常大，所以我們無法在RAM中擁有整個結構。存儲/檢索數據結構

enter image description here

IMAGE：這個詞BANANAS後綴樹（在我的情況下，設想一個樹大10萬次）。

因此，研究一下它，我發現pickle模塊是一個很棒的Python模塊，用於從文件中「加載」和「傾倒」對象，並猜測是什麼？它對我的數據結構非常有用。

因此，長話短說：在磁盤上存儲和檢索此結構的最佳策略是什麼？我的意思是，解決方案可能是將每個節點存儲在文件中並在需要時從磁盤加載它，但這不是最好的辦法（太多的磁盤訪問）。

腳註：雖然我已標記這個問題爲python，編程語言不是問題的重要組成部分，在磁盤存儲/檢索策略，是真正的重點。

來源

2011-11-28 juliomalegria

一個重要的問題是您是否要創建此結構*一次*並多次使用它，或者是否要創建它並*允許更新*。 –

@GregHewgill：基本上，只需要一個大的文本處理來創建結構，然後就可以使用它。順便提一下 – juliomalegria

- 使用cPickle - 酸菜快得多。也爲什麼不使用JSON，而是工作與磁盤工作對付nosql數據庫（我不是專家是這個主題告訴你哪一個，但NosSql是已知的解決方案，正是這種場景 - 很好，我相信比多個磁盤文件） – alonisser

如果pickle已經在爲您工作，您可能需要查看ZODB，它在pickle之上添加了一些功能。看看這個文檔，我看到這個段落的目的是解決你所面對的大小問題：

數據庫在內存和存儲之間自由移動對象。如果對象有一段時間沒有被使用，它可能會在下次使用時從內存中加載並釋放內容。

來源

2011-11-28 18:59:07 jcollado

感謝所有回答，在測試了所有選項並經過多次討論之後，我做出了我的決定：我將使用'ZODB'，一個非常有趣的模塊，如果您喜歡這種類型的模塊，請檢查一下。 – juliomalegria

將它存儲在sqlite？

SQLite的：

有高達2個TB的數據，
支持SQL查詢的支持，
是用於存儲應用程序內的數據大更換，
可以支持〜100K訪問（如果用於平均web應用程序），

因此，仔細研究此解決方案可能會更好，因爲它已被證明成爲在應用程序中存儲數據的有效方式。

來源

2011-11-28 18:42:32 Tadeck

感謝所有回答，在測試完所有選項並經過多次深思熟慮後，我做出了我的決定：我將使用'ZODB'，一個非常有趣的模塊，如果您喜歡這種類型的模塊，請檢查一下。 – juliomalegria

@ julio.alegria：好的，感謝分享解決方案:) – Tadeck

也許你可以結合cPickle和bsddb數據庫，它可以讓你將你的酸洗節點存儲在一個類似於字典的對象中，該對象將存儲在文件系統中;因此您可以稍後加載數據庫並從您需要的節點獲得真正出色的性能。

在一個非常簡單的方法：

import bsddb 
import cPickle 

db = bsddb.btopen('/tmp/nodes.db', 'c') 
def store_node(node, key, db): 
    db[key] = cPickle.dumps(node) 

def get_node(key, db): 
    return cPickle.loads(db[key])

來源

2011-11-28 18:48:22

感謝所有的答覆，經過測試你的所有選擇和經過大量的審議後，我做出了我的決定：我要使用'ZODB'，a非常有趣的模塊，如果你喜歡這種類型的東西，請檢查一下。 – juliomalegria

不錯的選擇:-) –

一種有效的方式來管理一個結構類似這樣是使用內存映射文件。在文件中，不是存儲節點指針的引用，而是將偏移量存儲到文件中。您仍然可以使用pickle將節點數據串行化爲適合存儲在磁盤上的流，但是您將希望避免存儲引用，因爲pickle模塊需要一次嵌入整個樹（如您所見）。

使用mmap模塊，可以將文件映射到地址空間並像讀取大量字節一樣讀取它。操作系統負責從文件中讀取文件，管理文件緩衝區和所有細節。

您可能會將第一個節點存儲在文件的起始位置，並具有指向下一個節點的偏移量。讀取下一個節點僅僅是從文件中正確的偏移量讀取的問題。

內存映射文件的優點是它們不是並不是一次加載到內存中，而是隻在需要時從磁盤讀取。我已經在一臺僅安裝了4GB內存的機器上完成了這項工作（在一個64位操作系統上），並且有一個30GB的文件，並且工作正常。

來源

2011-11-28 18:49:13

感謝所有的回答，經過測試所有的選擇和經過大量的審議後，我做出了我的決定：我要使用'ZODB'，一個非常有趣的模塊，檢查出來，如果你像這樣的事情。 – juliomalegria

試試看壓縮後的後綴樹。

其主要思想是代替1個字符的大量節點，可以將它們壓縮爲1個節點中的多個字符，從而節省額外的節點。

此處鏈接（http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml）表示您可以將160MB後綴樹轉換爲33MB壓縮後綴樹。收益頗豐。

這些壓縮樹被用於巨大字符串上的遺傳子字符串匹配。我以前用後綴樹的內存不足，但我壓縮後，內存不足錯誤消失。

我希望我能找到一個更好解釋實施的未付費文章。（http://dl.acm.org/citation.cfm?id=1768593）

來源

2011-12-16 03:10:58 Adrian

但即使樹被壓縮，它也必須存儲在磁盤中。根據你的數據的大小，最終是否是 – juliomalegria

。 DNA序列相當長，壓縮的後綴樹與它們一起工作（全部在內存中）。 – Adrian

存儲/檢索數據結構

回答

相關問題