GeoHash之存储篇

这篇具有很好参考价值的文章主要介绍了GeoHash之存储篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:

在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的,本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。


前缀树、跳表介绍:

什么是前缀树:

针对于没有接触过前缀树或者不熟悉前缀树的同学,我先简单介绍一下其基本原理。

前缀树 其主要就是分为两个部分 前缀 + 树

树大家肯定不陌生,比如二叉搜索树这样的数据结构就可以将查询效率降低至O(logn),
而前缀树不同之处在于它的节点的核心数据结构是这样的:

`

type Trie struct {
    child [26]*Trie
    isEnd bool
}

首先 child [26]*Trie主要作用就是存放子节点的,而isEnd作用就是去判断当前节点是否存在有一个完整的元素的结尾。光说原理比较枯燥,举例图示说明:

不知道大家是否了解过web后端路由是有哪些存储方式的,在golang语言中gin框架就是基于前缀树去存储路由的,比如:

假设我们要使用前缀树去存储
/ /ag /c /e这四个路由

那么存储过程就是应该这样的

image.png

每一个节点是一个Trie数据结构的节点,每个数组节点对应的是需要存储数据的单个字符,这样做的好处就是当我们需要存放的数据如果有相同前缀那么就不需要重复存储,节省空间,例如app、approach。那么app就只需要存储一次即可。

为了更方便理解,这里放一下插入元素、搜寻元素是否存在的代码:

func (this *Trie) Insert(word string)  {
    cur:=this
    for i:=0;i<len(word);i++{
        idx:=word[i]-'a'
        if cur.child[idx]==nil{
            cur.child[idx]=&Trie{}
            }
            cur=cur.child[idx]
    }
    cur.isEnd=true
}


func (this *Trie) Search(word string) bool {
    cur:=this
    for i:=0;i<len(word);i++{
        if cur.child[word[i]-'a']==nil{
                return false
            }
        cur=cur.child[word[i]-'a']
    }
    return cur.isEnd
}

而GeoHash得到的字符串其实正好满足大量相同前缀的特性,因此使用前缀树去存储GeoHash是相对比较合适的。


对于前缀树的补充

上述讲的其实是最基础版的前缀树,我们还可以对此进行一些魔改来优化存储与查询。

比如在Go/gin框架中的路由存储就是用的压缩前缀树

首先该树中当一个节点它仅有一个子节点时就会对树的结构进行一个压缩

image.png

/egg这个节点,e下子节点只有g,g下子节点就只有g,因此它们都会被合并到一起

其次句柄数量更多的 child node 摆放在 children 数组更靠前的位置.

如egg句柄数量更多,那么它就将会更靠前,以便于更早被遍历到


跳表原理简单介绍

其实用上述数据结构已经非常合适了,但是我为什么还要介绍一下SkipList这种数据结构呢,因为Redis中GEO 本身并没有设计新的底层数据结构,而是直接使用了 Sorted Set 集合类型。而Sorted Set底层其实就是跳表,那么就简单介绍一下。


链表在查找元素的时候,因为需要逐一查找,所以查询效率非常低,时间复杂度是O(N),于是就出现了跳表。跳表是在链表基础上改进过来的,实现了一种「多层」的有序链表,这样的好处是能快读定位数据。

如图所示

image.png

  • L0 层级共有 5 个节点,分别是节点1、2、3、4、5;
  • L1 层级共有 3 个节点,分别是节点 2、3、5;
  • L2 层级只有 1 个节点,也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素,只能从头开始遍历链表,需要查找 4 次,而使用了跳表后,只需要查找 2 次就能定位到节点 4,因为可以在头节点直接从 L2 层级跳到节点 3,然后再往前遍历找到节点 4。

可以看到,这个查找过程就是在多个层级上跳来跳去,最后定位到元素。当数据量很大时,跳表的查找复杂度就是 O(logN)


想要自己简单动手去实现一下跳表可以刷一下对应的题(力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台)

这里贴一下自己写的跳表代码文章来源地址https://www.toymoban.com/news/detail-683961.html

type Node struct {
	Val  int
	Next *Node
	Down *Node
}

type Skiplist struct {
	head *Node
}

func Constructor() Skiplist {
	return Skiplist{head:&Node{Val:-1,Next:nil,Down:nil} }
}

func (this *Skiplist) Search(target int) bool {
    curr:=this.head
    for curr!=nil{
        for curr.Next!=nil&&curr.Next.Val<target{
            curr=curr.Next
        }
        if curr.Next != nil&&curr.Next.Val==target{
            return true
        }
        curr=curr.Down
    }
    return false
}

func (this *Skiplist) Add(num int) {
    curr:=this.head
    isInsert:=true
    down:=&Node{Val:-1,Next:nil,Down:nil}
    deque:=[]*Node{}
    for curr!=nil{
        for curr.Next!=nil&&curr.Next.Val<num{
            curr=curr.Next
        }
        deque=append(deque,curr)
        curr=curr.Down
    }
    for len(deque)>0&&isInsert{
        curr=deque[len(deque)-1]
        deque=deque[:len(deque)-1]
        if down.Val==-1{
            curr.Next=&Node{Val:num,Next:curr.Next,Down:nil}
        }else{
            curr.Next=&Node{Val:num,Next:curr.Next,Down:down}
        }
        down=curr.Next
        isInsert=rand.Float64()>0.5
    }
    if isInsert{
        this.head=&Node{Val:-1,Next:nil,Down:this.head}
    }
}

func (this *Skiplist) Erase(num int) bool {
	curr, isFound := this.head, false
	for curr != nil {
		for curr.Next != nil && curr.Next.Val < num {
			curr = curr.Next
		}
		if curr.Next != nil && curr.Next.Val == num {
			isFound = true
            curr.Next = curr.Next.Next
		}
		curr = curr.Down
	}
	return isFound

}

到了这里,关于GeoHash之存储篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【OSS存储】阿里云的oss存储服务 & golang的API调用

    阿里云对象存储OSS(Object Storage Service)是一款海量、安全、低成本、高可靠的云存储服务,提供99.9999999999%(12个9)的数据持久性,99.995%的数据可用性。多种存储类型供选择,全面优化存储成本。 非常适合存储非结构化数据,例如 视频、图形、日志、文本文件以及各种App应用

    2024年02月05日
    浏览(57)
  • GeoHash——滴滴打车如何找出方圆一千米内的乘客?

    不知道大家是否思考过一个问题,在一些场景下(如大家在使用高德地图打车的时候,邻近的司机是如何知道你在他的附近并将你的打车通知推送给他去接单的?)是如何实现的? 一般来讲,大家也许会想到,首先肯定需要知道每位乘客的 经纬度(lng,lat) ,也即是二维坐标(

    2024年02月11日
    浏览(49)
  • golang一个轻量级基于内存的kv存储或缓存

    golang一个轻量级基于内存的kv存储或缓存 go-cache是一个轻量级的基于内存的key:value 储存组件,类似于memcached,适用于在单机上运行的应用程序。 它的主要优点是,本质上是一个具有过期时间的线程安全map[string]interface{}。interface的结构决定了它不需要序列化。基于内存的特性

    2024年02月02日
    浏览(73)
  • 为什么 Golang Fasthttp 选择使用 slice 而非 map 存储请求数据

    Fasthttp 是一个高性能的 Golang HTTP 框架,它在设计上做了许多优化以提高性能。其中一个显著的设计选择是使用 slice 而非 map 来存储数据,尤其是在处理 HTTP headers 时。 为什么呢? 本文将从简单到复杂,逐步剖析为什么 Fasthttp 选择使用 slice 而非 map,并通过代码示例解释这一

    2024年01月22日
    浏览(49)
  • 【golang】go获取腾讯云cos对象存储 并转为base64字符串输出

    需要引入腾讯云cos的sdk https://github.com/tencentyun/cos-go-sdk-v5 配置yaml如下: go代码编写如下:

    2024年02月11日
    浏览(54)
  • 【Golang星辰图】Go语言云计算SDK全攻略:深入Go云存储SDK实践

    在当今数字化时代,云计算和存储服务扮演着至关重要的角色,为应用程序提供高效、可靠的基础设施支持。本文将介绍几种流行的Go语言SDK,帮助开发者与AWS、Google Cloud、Azure、MinIO、 阿里云和腾讯云等各大云服务提供商的平台进行交互。 欢迎订阅专栏:Golang星辰图 1.1 提供

    2024年03月17日
    浏览(52)
  • 【golang函数笔记】

    Golang是一种支持函数式编程的语言,它的函数具有以下特点: 函数是一等公民:函数可以作为参数传递给其他函数,也可以作为返回值返回给调用者。 支持多返回值:函数可以返回多个值,这些值可以是不同类型的。 支持匿名函数:Golang支持定义匿名函数,这些函数可以像

    2024年02月16日
    浏览(22)
  • goLang笔记+beego框架

    初始安装之后 GOPATH: Go开发相关的环境变量如下: GOROOT: GOROOT 就是 Go的安装目录 ,(类似于java的JDK) GOPATH: GOPATH 是我们的 工作空间 ,保存go项目代码和第三方依赖包 GOPATH可以设置多个,其中,第一个将会是默认的包目录,使用 go get 下载的包都会在第一个path中的src目录下

    2024年02月09日
    浏览(36)
  • golang二分查找算法实现

    项目中使用到有序数组查找特定元素,简单记录下 Golang 中二分查找算法。 二分查找算法是一种在有序数组中查找特定元素的高效算法。它的基本思想是通过不断将查找范围缩小一半,来快速定位目标元素是否存在。该算法要求数组是有序的,这是因为有序数组的特性允许我

    2024年01月25日
    浏览(44)
  • golang实现关键路径算法

    关键路径算法(Critical Path Method,简称CPM)是一种用于项目管理的技术,主要用于计算项目中的关键路径和关键活动。关键路径是指项目中的最长路径,决定了项目的最短完成时间。关键活动是指在关键路径上的活动,必须按时完成才能确保项目按计划完成。 关键路径算法通

    2024年02月03日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包