liangxudongsun / algorthmgame

服务器端游戏中常见算法

AlgorthmGame

服务器端游戏中常见算法

##跳跃表

概念

是基于有序链表的扩展，提取出链表中关键节点作为索引的多层链表，以空间换时间提高查找性能。

时间及空间复杂度

算法	平均	最差
空间	O(n)	O(n log n)
搜索	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

应用

1.Redis的sorted set

2.LevelDB的memtable

3.排行榜

##限流器

Token Bucket

令牌桶算法是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。令牌桶算法的描述如下：

• 假设限制1秒钟生成2个令牌，则按照500毫秒的固定速率往桶中添加令牌；
• 桶中最多存放a个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
• 当有n个请求到达，将从桶中删除n个令牌，接着请求被发送到网络上；
• 如果桶中的令牌不足n个，则不会删除令牌，且该请求将被限流（要么丢弃，要么缓冲区等待）。

Leaky Bucket

漏桶算法是一个存放固定水滴的桶，按照固定速率流出水滴，可以用于流量整形和流量控制漏桶，算法的描述如下：

• 一个固定容量的漏桶，按照常量固定速率流出水滴；
• 如果桶是空的，则不需流出水滴；
• 可以以任意速率流入水滴到漏桶；
• 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。