我毕业时就业于福州的一家GIS公司,有幸遇到一个很好的导师,我的部门经理,在那时我第一次接触到了Google地图的金字塔模型。这个数据模型就是目 前我所使用的无限级索引数据结构的鼻祖,因为目前我已不再该公司工作,和朋友们一起出来创办了一家GPS行业的公司,所以在这里不对原公司所用的数据结构 做太详细的分析。
所谓的金字塔模型,实际上是一个四叉树,每一个层级的节点个数是(2^n)^2个,层级索引从0开始计数,第0级为1个节点,通常可以视为根节点,第1级 为(2^1)^2个节点即4个节点……以此类推。这刚好可以用来描述一个地图有规律的精细度区块划分。在第0级时,我们可以看到整个世界地图,在第1级的 时候,每一张图片我们只能1/4的世界地图,在第2级的时候,就只能看到1/8了,如下图
显然,这种几何式增长的数据量用文件系统来存储的话是很不明智的。
既然有如此规律的排布,用一种带索引的数据文件来存储的话,是一个非常好的办法,我们只要知道每一张图片的唯一标识,就可以通过索引来找到它。从上 图不难看出,层级编号和图片编号很自然地形成了一个唯一标识,在每一个层级中,图片的编号是唯一的,或者干脆说,在每一个层级中,这实际上就是一个行列式 排布,由此我们的每一个层级中的图片就有了它们之间的大小关系,如此这般,我们就可以用二分查找的方式来找到我们所需要的那一张图片。
这就是初步金字塔模型,目前原有的公司可能还在沿用这这种模型,未经同意,我这里不做代码做分析。接下来会进一步讲到这个数据模型是如何进化成“无限级索引的数据结构”,届时将分享源代码,可能还有需要改进的地方,我们可以一起讨论。