从googlemap的金字塔模型到无限级索引数据结构

《从googlemap的金字塔模型到无限级索引数据结构》由会员分享，可在线阅读，更多相关《从googlemap的金字塔模型到无限级索引数据结构（20页珍藏版）》请在金锄头文库上搜索。

1、从从 GoogleMap 的金字塔模型到无限级索引数据结构的金字塔模型到无限级索引数据结构 众所周知，现在很多网上的电子地图都使用矢量地图，用切图引擎切成栅格式的，存放与服务端，通过 URL 的方式访问，这对我们的 GIS 项目开发提供了一个非常好的地图来源，我们可以拥有自己的地图引擎， 只要知道切好的栅格图排布规律，就可以在完美的展现。但是往往在做 GIS 项目的时候会遇到一个问题：有 时候客户的机器并没有连接到互联网，或者有各种各样的问题，导致通过 URL 的方式访问地图速度会很慢， 更有一个大的问题， 有的地图供应商虽然开放免费的地图数据， 但对访问次数上做了限制， 比如说谷歌地图。 由

2、此就产生了众多的地图下载器下载地图。下载完的地图或者直接提供给客户，或者自架服务器来解除这种 限制。但网上很多地图下载器虽然提供下载功能，但是却没有提供一个很好的数据结构来存储地图，由此我 们引入这个话题。 我毕业时就业于福州的一家 GIS 公司，有幸遇到一个很好的导师，我的部门经理，在那时我第一次接触 到了 Google 地图的金字塔模型。这个数据模型就是目前我所使用的无限级索引数据结构的鼻祖，因为目前我 已不再该公司工作，和朋友们一起出来创办了一家 GPS 行业的公司，所以在这里不对原公司所用的数据结构 做太详细的分析。 所谓的金字塔模型，实际上是一个四叉树，每一个层级的节点个数是（2n）

3、2 个，层级索引从 0 开始计 数，第 0 级为 1 个节点，通常可以视为根节点，第 1 级为(21)2 个节点即 4 个节点以此类推。这刚好可 以用来描述一个地图有规律的精细度区块划分。 在第 0 级时， 我们可以看到整个世界地图， 在第 1 级的时候， 每一张图片我们只能 1/4 的世界地图，在第 2 级的时候，就只能看到 1/8 了，如下图 显然，这种几何式增长的数据量用文件系统来存储的话是很不明智的。 既然有如此规律的排布，用一种带索引的数据文件来存储的话，是一个非常好的办法，我们只要知道每 一张图片的唯一标识，就可以通过索引来找到它。从上图不难看出，层级编号和图片编号很自然地形成了一

4、 个唯一标识，在每一个层级中，图片的编号是唯一的，或者干脆说，在每一个层级中，这实际上就是一个行 列式排布，由此我们的每一个层级中的图片就有了它们之间的大小关系，如此这般，我们就可以用二分查找 的方式来找到我们所需要的那一张图片。 这就是初步金字塔模型， 目前原有的公司可能还在沿用这这种模型， 未经同意， 我这里不做代码做分析。 接下来会进一步讲到这个数据模型是如何进化成“无限级索引的数据结构”，届时将分享源代码，可能还有需 要改进的地方，我们可以一起讨论。 最初的金字塔模型是分为两个文件进行存储，一个是索引文件，另外一个是纯粹的数据文件，索引文件 存储了层级索引，以及图片单元索引，每一个索引

5、的键值从小到大排序。层级索引存储了自身索引值以及图 片单元索引在索引文件中的储位置（有点小绕口，那就再看一遍），数据单元索引存储了每个数据单元的索 引值以及每一个数据单元在数据文件中的存储位置。 层级索引的元素格式是固定的，索引值从 0 到 24，而图片单元索引的元素个数是不固定的，这种设计很 有针对性。 为 GoogleMap 的层级准备 25 个层级来存储已经是绰绰有余了， 而每一个层级中的图片单元个数不 固定的原因也很简单：并不是所有区域都有任意等级的图片单元。 如图所示： 这样的 删除时就显1.没有的具有针对性 显得有些疲惫有一个文件空间性的数据结构在 惫了。 间的复用机制在按顺序写入

6、制，导致在频入和查询图片单繁的修改过程单元上性能得程中，数据文得到了最大化文件变得庞大。， 但在需要修。 修改、 插入、2.双文件存储的特点导致在使用时需要打开 2 个文件句柄， 查询到图片单元进行读取的时候增加了磁盘寻 道时间，使用的时候也不是很方便。 3.使用文件流进行数据访问，导致在存储数据量大的时候，打开和关闭文件时速度变慢，同时两个程序在 修改文件时，很难保证数据完整性。 在了解现有的数据结构和存在的问题之后，我们就可以开始着手修改 这一节阐述了怎样复用空闲的文件存储区。 曾经有一段时间遇到这么一个需求:已下载的 Google 地图在用户看来不够详细， 很多标注点没有， 或者有 的路

7、已经不存在了却在地图上仍然显示着，有些最近刚新建的建筑在地图上没有体现出来，诸多原因引出了 最终的结果，这些不准确的地图信息必须被修正。 也就是说，要在现有地图的基础上进行修改或者替换。当 时我是这么解决这个问题的：当客户提出一些地图数据不准确的时候，我会要求客户提供当地的测绘数据， 拿到这些数据之后，使用程序按照 Google 地图的样式进行绘制，然后切块，将这些数据替换到地图包中去。 由此就产生了一个问题，原本存储这些地图数据的区块变成了没有索引指向的区块，当需要修改的地图区域 比较大的时候，这种区块就会大量产生，并且作为一个没有用的空间占用着磁盘导致数据文件臃肿无比，从 内存管理的角度上

8、来讲这是一块应该被复用的存储区。 复用这些存储区的思路很简单，每次在修改一块地图块的时候，将这些存储区记录下来，当下次有地图 块需要写入的时候优先从已记录的空闲存储区中查找符合大小的存储区，如果没有的话就将数据写到文件末 尾，否则使用这个存储区。 设计一个空闲空间管理器，这个管理器应该有如下特点： 1.能够快速找到一个大于或者等于指定大小的空闲空间 2.当取出一个空闲区域使用时，被截断的那一部分应该还是被标记为未使用 3.当新加入一个空闲区域时，应该自动和已有的空闲区域融合 为了能够快速找到符合大小的空闲区域，只要一个按照大小有序的空闲空间列表即可，然后使用二分查 找法查找。 取出一个空闲区域

9、使用时，我们只要重新把被截断的那部分空间重新加入空闲列表就可以满足第二点 自动融合新加入的空闲区域的意为：当新加入的空闲区域和已有的空闲区域连续的时候，应该自动合并 这两个空闲区域，并且重新调整列表。 / / 按照空间位置排序的空闲列表，该列表只有在添加空闲空间时才会作出改变,并且元素和Frees_Size是一样的，但是顺序不一样 / public readonly List Frees_Position = new List(); / / 按照空间大小进行排序的空闲列表，该列表只有在添加空闲空间时才会作出改变,并且元素和Frees_Position是一样的，但是顺序不一样 / public

10、readonly List Frees_Size = new List(); public void UnsafeAddRange(Range freeItem) if (freeItem.Start = freeItem.End) return; if (Frees_Position.Count 0) retest: /找到第一个起始位置比目标对象要大或者等于的元素 long index = SMath.BinarySearch(Frees_Position, (source, position, target) = Range cur = source(int)position; if (

11、cur.End = target.Start) return SentenceResult.Equal; if (cur.Start = target.End) return SentenceResult.Equal; if (cur.Start target.Start) return SentenceResult.More; if (cur.Start = 0 /已知的空间被需要添加的空间包含，那么直接剔除掉原有的空间，并且重新检测 if (item.Start freeItem.Start Frees_Size.Remove(item); Frees_Position.Remove(it

12、em); freeItem = item; goto retest; /或者尾首相连 if (item.End = freeItem.Start | (freeItem.Start item.Start Frees_Size.Remove(item); Frees_Position.Remove(item); freeItem = item; goto retest; /如果不满足以上的所有条件（即需要插入的空闲块和插入位置后面的那个空闲块没有交集） ，那么检测前一个空闲块和当前需要插 入的空闲块的关系 if (!preItemTested) preItemTested = true; if

13、(index 0) index; goto testPreItem; else /如果前后两个空闲块都检测过没有交集的时候，直接插入列表 Frees_Position.Insert(int)index, freeItem); item = freeItem; else index+; Frees_Position.Insert(int)index, freeItem); item = freeItem; /否则直接插入 else if (index = long.MinValue) Frees_Position.Insert(0, freeItem); else Frees_Position.

14、Add(freeItem); item = freeItem; /找到大小最相近的元素项,更新按照大小排序的列表 index = SMath.BinarySearch(Frees_Size, (source, position, target) = Range cur = source(int)position; if (cur.Size target.Size) return SentenceResult.More; else if (cur.Size = 0 else Frees_Size.Insert(int)index + 1, item); else if (index = long

15、.MinValue) Frees_Size.Insert(0, item); else Frees_Size.Add(item); OnRangeModifired(item); else Frees_Position.Add(freeItem); Frees_Size.Add(freeItem); OnRangeModifired(freeItem); 一个通用的二分查找算法 / / 在二分查找法中，指定判别方法的委托，该方法判别当前所指向的位置的数据和目标数据的大小关系, 例如:Position位置的数据大于目标值， 则返回More，如果相等则返回Equal，否则返回Less / publ

16、ic delegate SentenceResult StreamBinarySearchSentenceHandler(TSource stream, long position, TTarget value); / / 表示对两个值大小的判别结果, / More表示 Left Right, / public enum SentenceResult / / 大于 即: Left Right / More = 1, / / 等于 即: Left = Right / Equal = 0, / / 小于 即: Left Less = 1, / / 找到大于等于Value值的位置,如果目标元素大于所有集合对象，则返回