本文章是由機器翻譯。
SQL Server
經緯度資料的自訂索引
在這篇文章中，我描述了一種技術來創建包含緯度和經度位置資訊的地理資料的自訂索引。自訂索引允許快速、 即時檢索資料。例如，請考慮下面的情形。假設您有很大 （幾個億的專案） 設置的資料，看起來像這樣：
0001 47.610 -122.330
0002 36.175 -115.136
0003 47.613 -122.332
...
這裡的第一列是一個使用者 ID （或與位置相關聯的任何物件的 ID），第二列是使用者的緯度和第三列是使用者的經度。 緯度範圍從-90.0 度到 +90.0 度，並代表的上下座標。 經度的範圍從-180.0 度到 +180.0 度，並代表的左、 右座標。 西雅圖附近的第一和第三個使用者的位置。 赤道緯度值為零。 這種貫穿，位於英國格林威治子午線經度為零。 現在假設您的資料存儲在 SQL 表中與您要查找所有使用者都位於同一 1 度由 1 度矩形作為使用者 0001。 你可以用這樣一個簡單的 SQL 語句：
SELECT userID
FROM tblUsers
WHERE latitude >= 47.0 AND latitude < 48.0
AND longitude >= -123.0 AND longitude < -122.0
在許多情況下這種方法行之有效。 如果您需要即時性能 （也許回應時間小於 3 秒） 當您的資料的大小超過某個閾值 （具體取決於系統資源），然而，回應時間開始大幅度降低。
在這樣的情況下獲取即時性能的一種方法是將每個位置分配給一個部門 id。 假設你就能從最初的資料生成輔助表，看起來像這樣：
0001 49377
0002 45424
0003 49377
...
在這裡，第一列是使用者 ID 和第二列是一個部門 id。 現在如果部門 ID 編制索引，類似于下面的 SQL 語句將是非常快，即使您的資料集有數以億計的專案：
SELECT userID
FROM tblSectors
WHERE sector = 49377
到主資料集，部門 ID 充當一個自訂的索引。所以，真正的挑戰是編寫一個函數，接受緯度和經度，並返回一個部門。
為了更好地瞭解自訂索引的概念，看看在中的示例 Windows 的演示文稿的基礎 (WPF) 應用圖 1。該應用程式有嵌入的 Bing 地圖地圖控制項。後為中心的映射到華盛頓州雷德蒙德市、 中的位置和縮放我在地圖上按兩下。按兩下事件被連接到一個事件處理常式確定的緯度和經度的點擊，在按一下的位置放置一個紅色標記點。下一步，app 計算點擊的部門 ID 搜索與 1 億隨機使用者位置項的後端 SQL 資料庫然後發現八個使用者在同一部門。搜索時間是 0.36 秒 — — 漂亮的令人印象深刻的表現。
圖 1 自訂操作的空間索引
|
|
|
|
|
||||
Microsoft SQL Server 2008 具有複雜的空間索引功能你可以在剛才所述的情況中使用。而且，在許多情況下，使用 SQL Server 空間索引是您最佳的選擇。在至少兩個方案中，但是，創建自訂的索引是更好的方法。可以僅在 SQL 類型幾何或地理位置的列上創建第一、 空間索引。如果您有舊的資料庫或資料來源緯度和經度位置存儲為純數位值，這些值，請鍵入地理轉換可能不可行。第二，即使 SQL Server 2008 中的空間索引是功能極其強大，完全可自訂，在某些情況下您可能需要完全控制您的索引模式。
雖然創建自訂索引不是一個新的概念，可用幾個具體的例子。在本文的其餘部分，我將介紹如何創建和使用自訂索引完整的示例。要充分認識這篇文章，您需要有至少中級 C# 和 T-SQL 編碼技能。您可以從此處提供的示例為關鍵的 C# 代碼 archive.msdn.microsoft.com/mag201206Indexing。
映射到一個部門 ID 的緯度經度
有很多方法可以將一個緯度經度對映射到一個部門 id。我在此處描述的方法是最簡單的和最好的解釋是與關係圖中所示圖 2。在自訂索引方案中的第一個決定是選擇如何細分全球。在圖2我已經分為每個自由度 （行值） 和經度 （列） 的每度兩部分，如分數 = 0.5 中圖的左上角。這將導致 360 緯度間隔，從 [-90.0，-89.5) 到 [+89.5、 +90.0] 和 720 經度間隔，從 [-180.0，-179.5) 到 [+179.5、 +180.0]。我使用方括弧，意思是具有包容性和一個括弧，意思是獨佔。小部分值為 0.5，有 360 ＊ 720 = 259,200 部門編號為從 0 到 259,199。我命令從左至右，從上到下，部門，如中所示圖 2。
圖 1 自訂索引設計
較小的分數參數的值創建更多的時間間隔，每度，並生成更多行業。在此示例中使用相同的值的小數部分的緯度和經度的時間間隔，但如果是更好地適合您的資料分發，則可以使用不同的值。各部門不是所有同一地區，但是，正如我稍後解釋。如果您有 （latitude） 的行索引裡和列 （經度） 索引 ci，在相應的部門 ID sid 可以計算，如下所示：
sid = (ri * 360 * 1/fraction) + ci
例如，在圖 2，部門 1441年是與 2 行索引和列索引 1 關聯和計算是作為 (2 ＊ 360 ＊ 1/0.5) + 1 = (2 ＊ 720) + 1 = 1441。 這個詞 360 ＊ 1/分數確定多少列間隔中的每一行，然後乘以裡給在相應的行中的第一個部門 ID。 添加詞術語基本上 ci 列向右移動從相應的行的開頭，並提供最後的部門 ID 結果。
拼圖的最後一部分是要將一個行索引到的緯度值和經度值對應到一個列的索引。 天真的做法就是不簡單的線性搜索。 痛苦的過去非常大的資料集的經驗告訴我在這種情況下，一個二進位搜索是更好的方法。 這個想法是從開始為零的低指數，中間指數和高相等於最後一個可能索引。 下一步，確定相應的緯度 （或經度） 區間的中間索引。 如果目標緯度 （或經度） 落在間隔中，中間索引是正確的傳回值。 如果目標緯度 （或經度） 小於當前的間隔，則新的中間索引到一半之間移動低指數和舊的中間索引。 如果目標緯度 （或經度） 大於當前的間隔，新的中間索引到一半之間移動舊的中間指數和高指數。 重複此過程，直到找到正確的中間索引。
C# 方法的實現，接受一個緯度值和一小部分，並返回相應的行索引的 LatIndex 提出的圖3。 LonIndex 方法返回一個列的索引，經度的合作夥伴完全對稱只是常數 180 替換為 360，和常量-90.0 和 90.0-180.0 和 180.0 所取代。
圖 3 緯度的行/緯度的索引
static int LatIndex(double latitude, double fraction)
{
latitude = Math.Round(latitude, 8);
int lastIndex = (int)(180 * (1.0 / fraction) - 1);
double firstLat = -90.0;
if (latitude == -90.0) return 0;
if (latitude == 90.0) return lastIndex;
int lo = 0;
int hi = lastIndex;
int mid = (lo + hi) / 2;
int ct = 0; // To prevent infinite loop
while (ct < 10000)
{
++ct;
double left = firstLat + (fraction * mid); // Left part interval
left = Math.Round(left, 8);
double right = left + fraction; // Right part interval
right = Math.Round(right, 8);
if (latitude >= left && latitude < right)
return mid;
else if (latitude < left)
{
hi = mid - 1; mid = (lo + hi) / 2;
}
else
{
lo = mid + 1; mid = (lo + hi) / 2;
}
}
throw new Exception("LatIndex no return for input = " + latitude);
}
因為中的方法圖 3 作品同緯度地區作為類型雙，輸入的緯度參數四捨五入為八個小數位，以免出現噁心平等-的--類型雙層錯誤。 我使用某種程度上是經過 ct 變數來防止無限迴圈。 要保持代碼較短，我已經刪除大多數普通錯誤檢查 — — 如驗證的輸入的參數 — — 你會在生產方案中使用。 請注意，在表單中的時間間隔檢查主迴圈 [a,b)，所以我必須顯式檢查的最後 90.0 值。
在地方部門設計和説明器方法，可以映射一個緯度經度對到某個磁區與這樣的一種方法：
static int LatLonToSector(double latitude, double longitude,
double fraction)
{
int latIndex = LatIndex(latitude, fraction); // row
int lonIndex = LonIndex(longitude, fraction); // col
return (latIndex * 360 * (int)(1.0 / fraction)) + lonIndex;
}
磁區大小
我在本文中描述的自訂索引計畫分為基於分數參數的值的數值相等間隔的地球。 例如，如果分數為 0.5，每個時間間隔是 0.5 度的緯度或經度。 然而，這並不意味著所有部門都具有相同的地理區域。 看看圖 4。 緯度線運行彼此平行的並且是所有相同距離、 111 公里左右。 所以距離指示中的標籤 A 圖 4 是由 B.表示的距離相同 但經線靠近在一起時，它們每個極點附近。 所以距離通過標籤表示，C 是由 D.表示的距離小於
.jpg)
圖 4 部門有不同的地理區域
距離，以公里，地球上任何兩點之間可以用來估計下面的方法：
static double Distance(double lat1, double lon1,
double lat2, double lon2)
{
double r = 6371.0; // approx.
radius of earth in km
double lat1Radians = (lat1 * Math.PI) / 180.0;
double lon1Radians = (lon1 * Math.PI) / 180.0;
double lat2Radians = (lat2 * Math.PI) / 180.0;
double lon2Radians = (lon2 * Math.PI) / 180.0;
double d = r * Math.Acos((Math.Cos(lat1Radians) *
Math.Cos(lat2Radians) *
Math.Cos(lon2Radians - lon1Radians) +
(Math.Sin(lat1Radians) * Math.Sin(lat2Radians)));
return d;
}
所以如果您知道相應的緯度和經度給定的磁區，你可以計算出其近似的寬度和高度，然後及其近似的地區。 若要確定包含某一部門的時間間隔的左終結點，可以使用此方法：
static double SectorToLat(int sector,
double fraction)
{
int divisor = 360 * (int)(1.0 / fraction);
int row = sector / divisor;
return -90.0 + (fraction * row);
}
此方法基本上是執行方法 LatLonToSector 的逆過程。 例如，如果輸入的部門是 1441年和分數參數有 0.5 的值，如中所示圖 2，本地除數的變數是 360 ＊ 1.0 / 0.5 = 720，是的經度間隔數。 然後變數的行的值是 1441年 / 720 = 2，這是 （注意整數除法） 的行索引。 最後，-90.0 + 0.5 ＊ 2 =-90.0 + 1.0 =-89.0，這是在左邊的一部分 [-89.0，-79.5) 與部門 1441年相關聯的時間間隔。
該方法以確定左邊的部分的一個部門的經度間隔是類似但不是完全對稱：
static double SectorToLon(int sector, double fraction)
{
int divisor = 360 * (int)(1.0 / fraction);
int col = sector % divisor;
return -180.0 + (fraction * col);
}
與這兩個的説明器方法，您可以確定近似地區平方公里，一個部門，由部分參數已定義的：
static double Area(int sector, double fraction)
{
double lat1 = SectorToLat(sector, fraction);
double lon1 = SectorToLon(sector, fraction);
double lat2 = lat1 + fraction;
double lon2 = lon1 + fraction;
double width = Distance(lat1, lon1, lat1, lon2);
double height = Distance(lat1, lon1, lat2, lon1);
return width * height;
}
毗鄰的部門
在一些發展方案中，您可能需要確定哪些部門是連續的給定的磁區。 例如，在圖 2，如果使用者的位置是在部門 721，您可能想要確定哪些使用者在毗鄰的部門 0、 1、 2、 720、 722、 1440年、 1441年和 1442年。 請注意左、 右部門不同的加上或減去一，除了左和右邊緣的部門測繪部門。 上下行業、 部門的頂部和底部的行，但不同的加號或減號的列的時間間隔，數量是 360 ＊ （1 / 分數）。 要編寫接受一個部門 （和生成的一小部分） 的 AdjacentSectors 的一種方法，很有用，知道一個部門是左或右映射邊緣，還是在頂部或底部的行上。 這四種方法載于圖 5。
圖 5 的説明器方法的 AdjacentSectors 方法
static bool IsLeftEdge(int sector, double fraction)
{
int numColumns = (int)(1.0 / fraction) * 360;
if (sector % numColumns == 0) return true;
else return false;
}
static bool IsRightEdge(int sector, double fraction)
{
if (IsLeftEdge(sector + 1, fraction) == true) return true;
else return false;
}
static bool IsTopRow(int sector, double fraction)
{
int numColumns = (int)(1.0 / fraction) * 360;
if (sector >= 0 && sector <= numColumns - 1) return true;
else return false;
}
static bool IsBottomRow(int sector, double fraction)
{
int numColumns = (int)(1.0 / fraction) * 360;
int numRows = (int)(1.0 / fraction) * 180;
int firstValueInLastRow = numColumns * (numRows - 1);
int lastValueInLastRow = numColumns * numRows - 1;
if (sector >= firstValueInLastRow && sector <= lastValueInLastRow)
return true;
else
return false;
}
在很多方面，貿易關閉的清晰度和代碼的大小，您可以編寫方法 AdjacentSectors。 一種方法是返回一個部門值陣列位置 [0] 傳回值是連續的部門是左上角的輸入部門、 [1] 正上方、 [2] 是以上和向右、 [3] 向左、 [4] 是向右、 [5] 是下面和向左、 [6] 是下方，並 [7] 下和向右。 中的代碼圖 6 概述了執行 AdjacentSectors 的一種方法。 雖然一般情況下，輸入的部門並不是映射邊緣非常簡單的特殊的情況下，包括四個角的部門，有些棘手。 請參閱本文的完整實現的代碼下載。
圖 6 AdjacentSectors Method 的實現
static int[] AdjacentSectors(int sector, double fraction)
{
int[] result = new int[8]; // Clockwise from upper-left
int numCols = (int)(1.0 / fraction) * 360;
int numRows = (int)(1.0 / fraction) * 180;
int firstValueInLastRow = numCols * (numRows - 1);
int lastValueInLastRow = numCols * numRows - 1;
// General case
if (IsLeftEdge(sector, fraction) == false &&
IsRightEdge(sector, fraction) == false &&
IsTopRow(sector, fraction) == false &&
IsBottomRow(sector, fraction) == false)
{
result[0] = sector - numCols - 1;
result[1] = sector - numCols;
result[2] = sector - numCols + 1;
result[3] = sector - 1;
result[4] = sector + 1;
result[5] = sector + numCols - 1;
result[6] = sector + numCols;
result[7] = sector + numCols + 1;
return result;
}
// Deal with special cases here.
See code download.
throw new Exception("Unexpected logic path in AdjacentSectors");
}
放在一起地理的索引計畫
瞭解本文中描述的地理自訂索引計畫的好方法是檢查一個簡單但完整的端到端示例。 首次創建虛擬 SQL 資料庫使用 T-SQL 代碼類似于這樣：
use master
if exists(select * from sys.sysdatabases where name='dbGeoData')
drop database dbGeoData
create database dbGeoData on
(
name=dbGeoData,
filename='D:\SomePlace\dbGeoData.mdf'
)
接下來，創建一個表來保存一些虛擬的資料：
use dbGeoData
create table tblUsers
(
userID int primary key,
latitude real not null,
longitude real not null
)
然後編寫一些 C# 代碼，以生成虛擬資料：
Random r = new Random(0);
string initialDataFile = "..
\\..
\\UserIDLatLon.txt";
FileStream ofs = new FileStream(initialDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
for (int i = 0; i < 1000000; ++i)
{
double lat = (90.0 - (-90.0)) * r.NextDouble() + (-90.0);
double lon = (180.0 - (-180.0)) * r.NextDouble() + (-180.0);
sw.WriteLine(i.ToString().PadLeft(6,'0') + "," +
lat.ToString("F8") + "," + lon.ToString("F8"));
}
sw.Close(); ofs.Close();
在這裡我我創建以逗號分隔的資料 100 萬的線。 在該範圍中生成隨機的緯度和經度 [hi,lo)，我使用的標準模式 （hi-羅湖） ＊ 隨機。NextDouble() + 羅湖。 下一步，將虛擬資料複製到 SQL 表中使用命令列 bcp.exe 程式：
> bcp.exe dbGeoData..tblUsers in UserIDLatLon.txt -c -t , -r \n -S(local) -T
此命令的手段，"將複製到表 tblUsers，這是在資料庫 dbGeoData，UserIDLatLon.txt，這是字元資料 （即，文字檔） 其中每一列是由逗號分隔的終止，每一行都是由一個分行符號回報終止檔中的資料。 資料庫伺服器可以在本地電腦上，和信任 (Windows) 身份驗證用於連接"。
然後創建輔助自訂索引部門資料使用 C# 這樣的代碼：
string initialDataFile = "..
\\..
\\UserIDLatLon.txt";
string sectorDataFile = "..
\\..
\\ UserIDSector.txt";
FileStream ifs = new FileStream(initialDataFile, FileMode.Open);
StreamReader sr = new StreamReader(ifs);
FileStream ofs = new FileStream(sectorDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
string line = "";
string[] tokens = null;
while ((line = sr.ReadLine()) != null)
{
tokens = line.Split(',');
int userID = int.Parse(tokens[0]);
double lat = double.Parse(tokens[1]);
double lon = double.Parse(tokens[2]);
int sector = LatLonToSector(lat, lon, 0.5);
sw.WriteLine(userID.ToString().PadLeft(6, '0') + "," + sector);
}
sw.Close(); ofs.Close(); sr.Close(); ifs.Close();
代碼通過虛擬資料檔案一線迴圈一次 ； 解析出的使用者 ID、 緯度和經度 ； 計算的 0.5 ； 小部分參數的相關的部門 寫入操作的使用者 ID 和部門在以逗號分隔的表單，到一個文字檔中。
接下來，創建一個 SQL 表來保存的部門資料：
create table tblSectors
(
userID int primary key,
sector int
)
然後將部門的資料複製到表中：
> bcp.exe dbGeoData..tblSectors in UserIDSector.txt -c -t , -r \n -S(local) -T
最後，索引部門資料：
if exists(select name from sys.sysindexes where name='ndxSector')
drop index ndxSector on tblSectors
create nonclustered index ndxSector on tblSectors(sector)
此時您可以通過幾種方法進行試驗。 例如，您可以選擇所有使用者都在同一部門作為使用者 3 T-SQL 代碼，如下所示：
declare @userID int
set @userID = 3
declare @sector int
select @sector = sector from tblSectors where userID=@userID
print @sector
select userID from tblSectors where sector = @sector
當然，如果您正在訪問您的 SQL 資料從應用程式中，您可以使用 ADO.NET 或 LINQ 等同于這一類的 SQL 代碼。
獲取即時性能
您可以使用自訂索引在很多應用程式方案。例如，假設您有一個 ASP.NET Web 應用程式或使用 Bing 地圖中的 Silverlight 應用，映射控制。您可以創建一個系統，允許使用者按一下地圖上。與代碼是確定的緯度和經度的點擊的計算，相關聯的部門，然後從後端 SQL 資料庫中檢索該部門中的所有使用者相關聯的 click 事件。如中所示圖 1，甚至用幾個 1 億行你可以即時性能。
在某些情況下您可能想要創建自訂的幾個指標。例如，您可能希望與分數低細微性指數 = 1.0 （以便每個磁區是由 1 度 1 度），mid-granularity 指數與分數 = 0.25 和分數高細微性指數 = 0.05。具有多個索引可以先後篩選您的 SQL 資料。首先確定有多少使用者是在低細微性部門。如果您有太多的使用者對您的目的，確定有多少使用者中，mid-granularity 的部門。如果你有過幾個使用者，確定七個毗鄰的部門，這些部門中的使用者。等等等等。
讓我重申 SQL Server 2008 有強大內置空間索引您應該考慮使用之前創建自訂的索引。自訂索引需要明確的其他 SQL 表，您的系統上增加的管理負擔。儘管如此，但是，在某些情況下，自訂索引會導致閃電般的工作快的性能。具有 GPS 功能的手機越來越多地使用，收集大量的地理資料的能力只打算展開。創建自訂的索引方案的能力可以是一項重要的技能來説明您分析此資料。
Dr. James McCaffrey 作品為伏資訊科學，凡他管理著技術訓練的軟體工程師工作在華盛頓雷德蒙的微軟校園。他曾對幾個 Microsoft 產品，包括互聯網資源管理器和 MSN 搜索。麥卡弗裡也是作者的".NET 測試自動化食譜"（很，2006年）。他可以達到 jammc@microsoft.com。
由於下面的技術專家，檢討這篇文章：Isaac Kunen 和 Dan Liebling