以類似SAX的方式從磁盤進行二進制搜索XML - 明智嗎？可能？

Question

我發現自己需要通過一個（可能）大的XML文件來搜索具有特定時間戳的項目，以幀內動畫幀類型的速度進行搜索。

我已經做在最近的一個項目類似的東西，但那裏的XML足夠小，以適應在內存中，所以我分析出來爲簡單對象和數組的二進制搜索它。繁榮！超快速搜索每幀800多個時間戳項目。

這一次，在XML文件很可能是大到足以解析出來到內存中一個愚蠢的想法（這是iOS的東西，所以內存是有限的）。我腦海中的解決方案是從文件中進行類似SAX的流解析，但是使用可設置的指針。所以我可以在另一個二進制搜索中圍繞文件跳轉該指針，解析文件中的下一個完整節點，並使用它來通知搜索指針下一個跳轉的位置。

一個好的理論，我想。然而，環顧網絡，我一直無法找到一個允許在文件中設置當前行號的SAX解析器。很多人會以只讀方式訪問狀態，但是沒有人允許這種非常關鍵的位置設置。

SO。有誰知道有這樣的能力的XML解析庫嗎？再說一遍，這是iOS世界，所以基於C/C++的任何東西都可以做，但如果它有Obj-C包裝，則可以獲得獎勵。

Answer 1

你不能這樣做，安全地XML，至少沒有直接。你說你想跳到某個行號，但這可能對你沒有幫助，因爲XML不是基於行的。而且你不能輕易跳到某個節點的子節點n，因爲這需要完全解析XML。你可以做的是首先解析整個文件並創建一個索引：對於每個需要跳轉到的節點，你都記得它在文件中的起始位置（可能是字節偏移量）。你可以使用SAX（或類SAX）解析器來做到這一點，你不需要將整個文檔放在內存中。

如果你這樣做，你必須解析整個文件一次（O（n）操作），但你可以跳轉任何節點並快速解析（在O（1）中），這應該使二進制搜索性能。

或者你可以根據你要搜索的屬性創建索引。如果你這樣做，整個二進制搜索將在內存中，你可以解析你需要的一個（或幾個）節點，這應該更快。