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 度，用左右坐标表示。 第一个和第三个用户的位置在西雅图附近。 纬度值 0 表示赤道。 经度 0 表示本初子午线，它经过英国的格林威治。 现在，假设您的数据存储在 SQL 表中，并且您希望将位于同一 1 度 x 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 将作为主数据集中的自定义索引。 因此，真正的难题是编写一个接受纬度和经度并返回区域的函数。
为了更好地理解自定义索引概念，让我们看一下图 1 中的示例 Windows Presentation Foundation (WPF) 应用程序。 该应用程序具有一个嵌入式必应地图控件。 在将地图中心位置指定为华盛顿州雷德蒙德市并放大地图后，我在地图上双击鼠标按钮。 双击事件将绑定到一个事件处理程序，它确定单击位置的纬度和经度，并在单击位置添加一个红色标记点。 接下来，该应用程序计算单击位置的区域 ID，然后搜索包含 1 亿个随机用户位置项目的后端 SQL 数据库，并在同一区域中找到 8 个用户。 搜索时间为 0.36 秒，这说明搜索性能非常好。
.jpg)
图 1 正在执行的自定义空间索引
Microsoft SQL Server 2008 具有一项先进的空间索引功能，您可以在刚才介绍的情况中使用该功能。 在很多情况下，使用 SQL Server 空间索引是您的最佳选择。 然而，至少在两种情况下，创建自定义索引是更好的方法。 第一种情况是，只能在 SQL 类型几何或地理数据列上创建空间索引。 如果具有将纬度和经度存储为纯数值的遗留数据库或数据源，则根本无法将这些值转换为地理数据类型。 第二种情况是，即使 SQL Server 2008 中的空间索引功能非常强大且可高度定制，在某些情况下，您也可能需要完全控制您的索引方案。
虽然创建自定义索引并不是什么新概念，但具体的示例并不多。 在本文的其余部分中，我将介绍一个说明如何创建和使用自定义索引的完整示例。 要充分理解本文，您至少需要具有中等 C# 和 T-SQL 编码技能。 您可以从 archive.msdn.microsoft.com/mag201206Indexing 获取此处介绍的示例的关键 C# 代码。
将纬度和经度映射到区域 ID
可以使用多种方法将纬度和经度对映射到区域 ID。 我在此处介绍的方法是最简单的，图 2 所示的图表清楚地说明了该方法。 有关自定义索引方案的第一个决定是，选择如何划分地球区域。 在图 2 中，我将每个纬度（行值）和每个经度（列）分为两个部分，如图左上角的 fraction = 0.5 所示。 这将产生 360 个纬度区间（[-90.0, -89.5) 至 [+89.5, +90.0]）和 720 个经度区间（[-180.0, -179.5) 至 [+179.5, +180.0]）。 我用方括号表示包括该值，而用圆括号表示不包括该值。 当 fraction 值为 0.5 时，共有 360 * 720 = 259,200 个区域，编号从 0 至 259,199。 我按从左到右和从上到下的顺序排列区域，如图 2 所示。
图 2 自定义索引设计
|
|
|
|
|
||||
较小的 fraction 参数值将为每度创建更多的区间，并生成更多的区域。 在此示例中，我对纬度和经度区间使用相同的 fraction 值，但如果不同的值更符合您的数据分布要求，则也可以使用不同的值。 然而，正如我要简要解释的一样，区域并非具有完全相同的面积。 如果行（纬度）索引为 ri，和列（经度）索引为 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/fraction 项确定每行中包含的列区间数，将其乘以 ri 可以得出相应行中的第一个区域 ID。 实际上，加上 ci 项会将 ci 列向右移动（从相应行的开头起），并得出最终的区域 ID 结果。
谜题的最后一部分是，将纬度值映射到行索引，而将经度值映射到列索引。 一个幼稚的做法是，执行简单的线性搜索。 过去处理大型数据集的惨痛教训告诉我，在这种情况下，二分法搜索是一种更好的方法。 其原理是从低索引 0 开始，中间索引和高索引等于上一个可能的索引。 接下来，确定中间索引的相应纬度（或经度）区间。 如果目标纬度（或经度）位于区间内，则中间索引就是正确的返回值。 如果目标纬度（或经度）小于当前区间，则将新的中间索引移到低索引和旧中间索引的中间位置。 如果目标纬度（或经度）大于当前区间，则将新的中间索引移到旧中间索引和高索引的中间位置。 重复该过程，直至找到正确的中间索引。
图 3 显示了方法 LatIndex 的 C# 实现，它接受纬度值和 fraction 并返回相应的行索引。 返回经度列索引的配对 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 中的方法适用于双精度类型的纬度，因此，输入纬度参数将四舍五入为 8 位小数，以避免讨厌的“两个数完全相等”类型双精度错误。 我使用类似二次修改的 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;
}
区域大小
我在本文中介绍的自定义索引方案根据 fraction 参数值将地球划分为数值相等的区间。 例如，如果 fraction 为 0.5，则每个区间为一个纬度或经度的一半。 然而，这并不意味着所有区域具有相同的地理面积。 请看一下图 4。 纬度线彼此平行并相隔相同的距离（大约 111 公里）。 因此，图 4 中的标签 A 表示的距离与标签 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，并且 fraction 参数具有值 0.5（如图 2 所示），则局部变量 divisor 为 360 * 1.0 / 0.5 = 720（这是经度区间数）。 因此，变量 row 的值是 1441 / 720 = 2，它是行索引（请注意结果是整除的）。 最后，-90.0 + 0.5 * 2 = -90.0 + 1.0 = -89.0，这是与区域 1441 相关的 [-89.0, -79.5) 区间的左侧部分。
确定区域的经度区间左侧部分的方法是类似的，但不完全对称：
static double SectorToLon(int sector, double fraction)
{
int divisor = 360 * (int)(1.0 / fraction);
int col = sector % divisor;
return -180.0 + (fraction * col);
}
通过使用这两个帮助程序方法，您可以确定 fraction 参数定义的区域的大致面积（平方公里）：
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 中。 请注意，左侧和右侧区域相差正 1 或负 1，但区域映射的左和右边缘上的区域除外。 上下区域相差正或负列区间数（等于 360 * (1 / fraction)），但顶部和底部行上的区域除外。 要编写接受区域（和生成拆分部分）的 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 方法实现
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");
}
创建地理索引方案
要了解本文中介绍的自定义地理索引方案，一种很好的办法是分析一个简单但完整的端到端示例。 首先，使用类似下面的 T-SQL 代码创建一个虚拟 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 - lo) * random.NextDouble() + lo。 然后，使用命令行 bcp.exe 程序将虚拟数据复制到 SQL 表中：
> bcp.exe dbGeoData..tblUsers in UserIDLatLon.txt -c -t , -r \n -S(local) -T
此命令意味着，“将文件 UserIDLatLon.txt 中的数据复制到位于数据库 dbGeoData 中的表 tblUsers，这些数据是字符数据（即，该文件是文本文件），其中，每列以逗号字符分隔，每行以换行符结束。 数据库服务器位于本地计算机上，并使用受信任的 (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、纬度和经度；使用 fraction 参数值 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)
此时，您可以尝试几种不同的方法。 例如，您可以使用类似下面的 T-SQL 代码选择与用户 3 位于同一区域中的所有用户：
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 数据，您可以使用与此类 SQL 代码等效的 ADO.NET 或 LINQ 代码。
获得实时性能
您可以在很多应用场景中使用自定义索引。 例如，假设您使用具有必应地图控件的 ASP.NET Web 应用程序或 Silverlight 应用程序。 您可以创建一个系统以允许用户在地图上单击鼠标按钮。 与单击事件相关的代码确定单击位置的纬度和经度，计算相关的区域，然后从后端 SQL 数据库中检索区域内的所有用户。 正如图 1 所示，甚至在处理几亿行数据时，您也可以获得实时性能。
在某些情况下，您可能需要创建几个自定义索引。 例如，您可能需要使用 fraction = 1.0 创建一个低粒度索引（因此，每个区域为 1 x 1 度），使用 fraction = 0.25 创建一个中粒度索引，以及使用 fraction = 0.05 创建一个高粒度索引。 通过使用多个索引，您可以连续筛选 SQL 数据。 首先，确定低粒度区域中有多少个用户。 如果对您来说用户太多，请确定中粒度区域中有多少个用户。 如果用户太少，请确定 7 个相邻的区域以及这些区域中有多少个用户。 其他在此就不一一列举了。
重申一下，SQL Server 2008 具有强大的内置空间索引功能，在创建自定义索引之前，应考虑使用该功能。 自定义索引需要明确的附加 SQL 表，这会增加系统上的管理负担。 但这也表明，在某些情况下，自定义索引可以获得极快的性能。 随着支持 GPS 的移动设备的使用越来越普遍，对收集大量地理数据的功能要求必定会持续增加。 能够创建自定义索引方案可能是一项重要技能，以便帮助您分析这些数据。
James McCaffrey博士供职于 Volt Information Sciences，负责管理华盛顿州雷德蒙德市 Microsoft 总部园区的软件工程师的技术培训工作。 他曾参与过多项 Microsoft 产品的研发工作，其中包括 Internet Explorer 和 MSN Search。 McCaffrey 还是《.NET Test Automation Recipes》（Apress，2006 年）的作者。 可通过 jammc@microsoft.com 与他联系。
衷心感谢以下技术专家对本文的审阅： Isaac Kunen 和 Dan Liebling