β

空间实时搜索引擎

KunBetter's World ! 154 阅读

Github地址(用go语言实现,还有很多需要改进的地方,请大家多多提意见!)

非实时索引及搜索

  包含经纬度的空间数据,可以用于地理方位标识。通过经纬度范围搜索包含在其中的数据,成为空间搜索,与传统的字符搜索不同。
  空间搜索采用四叉树划分算法,将每条数据划分的四叉树每一层的网格中。如果不需要实现实时索引及搜索功能的话,可以将所以数据看成是一个数组,然后按照从前到后第一、第二、第三、第四象限划分。对每一个象限,依次递归。一般递归十层即可。搜索时,对于给定的矩形(其他形状均可转化为矩形),计算其包含的四叉树的网格,即可获得该网格下所包含的数据。

实时索引及搜索

  实时索引及搜索时,如果还是按照上述算法,显然无法达到实时性。所以实时算法需要依据上面的算法进行改动。
  索引时,对于每一条新读取的数据,直接计算其对应的四叉树底层网格的ID号,然后将<底层网格ID,数据ID>保存到内存中。等内存数据到达一定数目的时候,再写到文件中。
  搜索时,和非实时算法差不多,只是如果计算获取的网格非底层网格时,需要将此网格换算成底层网格ID数组。由于非底层网格对应的底层网格数组的ID号是连续的,所以只需要计算对应的底层网格数组的起始和终止ID即可,即只需要计算一个区间即可。然后分别在内存和文件中读取相应的数据。而内存索引数组是分两个存储区的,一个用于写实时数据,另一个为只读,用于切换内存区及写文件。

Github地址(用go语言实现,还有很多需要改进的地方,请大家多多提意见!)

非实时索引及搜索

  包含经纬度的空间数据,可以用于地理方位标识。通过经纬度范围搜索包含在其中的数据,成为空间搜索,与传统的字符搜索不同。
  空间搜索采用四叉树划分算法,将每条数据划分的四叉树每一层的网格中。如果不需要实现实时索引及搜索功能的话,可以将所以数据看成是一个数组,然后按照从前到后第一、第二、第三、第四象限划分。对每一个象限,依次递归。一般递归十层即可。搜索时,对于给定的矩形(其他形状均可转化为矩形),计算其包含的四叉树的网格,即可获得该网格下所包含的数据。

实时索引及搜索

  实时索引及搜索时,如果还是按照上述算法,显然无法达到实时性。所以实时算法需要依据上面的算法进行改动。
  索引时,对于每一条新读取的数据,直接计算其对应的四叉树底层网格的ID号,然后将<底层网格ID,数据ID>保存到内存中。等内存数据到达一定数目的时候,再写到文件中。

作者:KunBetter's World !
Play And Study !
原文地址:空间实时搜索引擎, 感谢原作者分享。

发表评论