吉林响应式网站建设,乐都营销型网站建设,h5游戏平台代理,家具营销策划方案前言#xff1a;
在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的#xff0c;本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。 前缀树、跳表介绍#xff1a; …前言
在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。 前缀树、跳表介绍
什么是前缀树
针对于没有接触过前缀树或者不熟悉前缀树的同学我先简单介绍一下其基本原理。
前缀树 其主要就是分为两个部分 前缀 树
树大家肯定不陌生比如二叉搜索树这样的数据结构就可以将查询效率降低至O(logn), 而前缀树不同之处在于它的节点的核心数据结构是这样的 type Trie struct {child [26]*TrieisEnd bool
}
首先 child [26]*Trie主要作用就是存放子节点的而isEnd作用就是去判断当前节点是否存在有一个完整的元素的结尾。光说原理比较枯燥举例图示说明 不知道大家是否了解过web后端路由是有哪些存储方式的在golang语言中gin框架就是基于前缀树去存储路由的比如 假设我们要使用前缀树去存储 / /ag /c /e这四个路由
那么存储过程就是应该这样的 每一个节点是一个Trie数据结构的节点每个数组节点对应的是需要存储数据的单个字符这样做的好处就是当我们需要存放的数据如果有相同前缀那么就不需要重复存储节省空间例如app、approach。那么app就只需要存储一次即可。
为了更方便理解这里放一下插入元素、搜寻元素是否存在的代码
func (this *Trie) Insert(word string) {cur:thisfor i:0;ilen(word);i{idx:word[i]-aif cur.child[idx]nil{cur.child[idx]Trie{}}curcur.child[idx]}cur.isEndtrue
}func (this *Trie) Search(word string) bool {cur:thisfor i:0;ilen(word);i{if cur.child[word[i]-a]nil{return false}curcur.child[word[i]-a]}return cur.isEnd
}
而GeoHash得到的字符串其实正好满足大量相同前缀的特性因此使用前缀树去存储GeoHash是相对比较合适的。 对于前缀树的补充
上述讲的其实是最基础版的前缀树我们还可以对此进行一些魔改来优化存储与查询。
比如在Go/gin框架中的路由存储就是用的压缩前缀树
首先该树中当一个节点它仅有一个子节点时就会对树的结构进行一个压缩 /egg这个节点e下子节点只有gg下子节点就只有g因此它们都会被合并到一起
其次句柄数量更多的 child node 摆放在 children 数组更靠前的位置.
如egg句柄数量更多那么它就将会更靠前以便于更早被遍历到 跳表原理简单介绍
其实用上述数据结构已经非常合适了但是我为什么还要介绍一下SkipList这种数据结构呢因为Redis中GEO 本身并没有设计新的底层数据结构而是直接使用了 Sorted Set 集合类型。而Sorted Set底层其实就是跳表那么就简单介绍一下。 链表在查找元素的时候因为需要逐一查找所以查询效率非常低时间复杂度是O(N)于是就出现了跳表。跳表是在链表基础上改进过来的实现了一种「多层」的有序链表这样的好处是能快读定位数据。
如图所示 L0 层级共有 5 个节点分别是节点1、2、3、4、5L1 层级共有 3 个节点分别是节点 2、3、5L2 层级只有 1 个节点也就是节点 3 。 如果我们要在链表中查找节点 4 这个元素只能从头开始遍历链表需要查找 4 次而使用了跳表后只需要查找 2 次就能定位到节点 4因为可以在头节点直接从 L2 层级跳到节点 3然后再往前遍历找到节点 4。
可以看到这个查找过程就是在多个层级上跳来跳去最后定位到元素。当数据量很大时跳表的查找复杂度就是 O(logN) 想要自己简单动手去实现一下跳表可以刷一下对应的题(力扣LeetCode官网 - 全球极客挚爱的技术成长平台)
这里贴一下自己写的跳表代码
type Node struct {Val intNext *NodeDown *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.headfor curr!nil{for curr.Next!nilcurr.Next.Valtarget{currcurr.Next}if curr.Next ! nilcurr.Next.Valtarget{return true}currcurr.Down}return false
}func (this *Skiplist) Add(num int) {curr:this.headisInsert:truedown:Node{Val:-1,Next:nil,Down:nil}deque:[]*Node{}for curr!nil{for curr.Next!nilcurr.Next.Valnum{currcurr.Next}dequeappend(deque,curr)currcurr.Down}for len(deque)0isInsert{currdeque[len(deque)-1]dequedeque[:len(deque)-1]if down.Val-1{curr.NextNode{Val:num,Next:curr.Next,Down:nil}}else{curr.NextNode{Val:num,Next:curr.Next,Down:down}}downcurr.NextisInsertrand.Float64()0.5}if isInsert{this.headNode{Val:-1,Next:nil,Down:this.head}}
}func (this *Skiplist) Erase(num int) bool {curr, isFound : this.head, falsefor curr ! nil {for curr.Next ! nil curr.Next.Val num {curr curr.Next}if curr.Next ! nil curr.Next.Val num {isFound truecurr.Next curr.Next.Next}curr curr.Down}return isFound}
