哪個Java數據對象用於多維範圍匹配？

Question

項目背景： 我正在爲可以使用gdal2tile.py瓷磚的java編寫地圖貼圖疊加類。基本上，我將最終得到數以千計的文件結構像 「縮放級別/ X座標/ Y座標」的文件 座標是整數，但不一定會從0或1開始。 我將不得不搜索在一定範圍內的瓦片來找出我需要渲染哪些瓦片。

我的問題： 我嘗試迭代使用文件結構本身，但它是邪惡的慢（不奇怪）。 我試着迭代使用文件結構和.contains（）的字符串的ArrayList，但它似乎更慢（不太令人吃驚）。 最好我想使用一個數據結構，讓我可以在多個維度上選擇一個範圍，這樣我就可以調用類似的東西。 Tiles.getWhere（Zoom Level，min X，max X，min Y，maxY）; Tiles.getWhere（Zoom Level，min X，max X，min Y，maxY）;

我認爲某種集合或TreeMap將是正確的選擇，但是我沒有足夠的經驗來充分了解Java，並且我不希望對很多不同的方法進行基準測試。

我可以使用SQLite來做到這一點，但這似乎是矯枉過正。

我的問題： 什麼是最有效的方法來檢查數據集的存在給定多維約束？

Answer 1

也許你正在尋找一個有多個鍵的地圖。

共享的集合提供地圖與多個查找鍵：

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/MultiKeyMap.html

地圖保證了O（1）的插入和O（1）選擇的定時。

Answer 2

思考你的問題我可以找出三個方向，你可以瞄準你的搜索下一個（這不是一個手動的指南，而是一個開箱即用的開箱器，你面對）：

1） Java內置結構的使用。是的，的確，列表是搜索方法的最壞情況。顧名思義，Map對地圖來說更方便。它不僅是名稱，而且與List相比，Map的索引耗時更少。如果您使用List，並且可能只有當您通過索引Map進行搜索時，它可能只有一小部分，您可以將您的地圖想象成一個立方體，在那裏您必須處理其中一半的點。有一個巨大的差異。所以，我的答案在這裏：Map是一個關鍵詞朝着正確的方向（假設你想這樣做後閱讀我的答案）。

2）使用Map Server解決方案。這可能與您的方法相距甚遠，但整個框架都是爲了解決您的問題而設計的。一個例子是GeoServer。它爲整個問題提供了一個現成的解決方案。對於您手中可能遇到的重大問題，這是一個穩定的解決方案：從源代碼向用戶顯示地圖。

3）堅持你使用GDAL框架，你可以選擇稍微不同的PY-文件，像gdal_proximity.py和- 哇！ -你有一種可能性在你的手中！這個特定的搜索中心點和距離，但會做你需要的東西=）

有一個起點，我會怎麼做。這可以爲某些東西服務嗎？

Answer 3

聽起來像我一樣，你正在尋找像一個間隔樹。

http://en.wikipedia.org/wiki/Interval_tree

我已經實現了其中的一個，在過去，但只有在一個維度。維基百科參考文件提到了更多維度的擴展。

Paul