Go面试看这里了~(二十五)

原文地址:Go面试看这里了~(二十五)

1、PostgreSQL优点?

Postgresql比MysqL更加庞大,因为其是用来替代Oracle而设计,优点如下:

  1. 继承表-解决实际中的主子表各类问题。

  2. 并发创建索引。

  3. 数组类型。

  4. JSONB类型。

  5. 瞬间添加无默认值新列。

2、top K问题?

在海量数据中找出出现频率最高的前K个数,或从海量数据中找出最大的前K个数,此类问题通常被称为top K问题,像在搜索引擎中统计搜索最热门的10个查询词、在歌曲库中统计下载最高的前10首歌等。

解决此类问题可建立大小为K小根堆,然后从第K个元素开始遍历,如大于小根堆堆顶,就交换两元素,交换一次调整一次,直到所有数据遍历结束,堆中元素就是海量数据中最大的K个,因为小根堆堆顶是最小的值,当遍历剩余数据时,只有大于此堆中最小值才可放进来,当遍历结束后堆中元素就是最大的K个。

3、Redis跳跃表数据结构?

跳跃表(SkipList):使用空间换时间的策略,通过给链表建立多层索引来加快搜索效率,可用下图加深理解。

Go面试看这里了~(二十五)

数据结构如下:

typedef struct zskiplist {    struct zskiplistNode *header, *tail;    unsigned long length;    int level;} zskiplist;

跳表中每个节点用zskiplistNode数据结构表示,head和tail分别指向最底层链表头尾节点,length为当前跳表最底层链表有多少个节点,level记录当前跳表最高索引层数。

来看zskiplistNode的数据结构:

typedef struct zskiplistNode {    sds ele;    double score;    struct zskiplistNode *backward;    struct zskiplistLevel {        struct zskiplistNode *forward;        unsigned int span;    } level[];} zskiplistNode;

此处摘取redis4.0源码,前版本ele属性是RedisObject,现在是字符串,表示跳表只用于存储字符串数据,score记录当前节点一个分值,最底层链表就是按照分值大小有序的串联,查询一个节点,一般也会传入该节点的score值,backward 指针指向前一个节点,level是较关键点,是一个level数组,而每个元素又都是一个zskiplistLevel类型的结构,zskiplistLevel类型包括一个forward前向指针,一个span跨度值。

跳表理论上在最底层是一条双端链表,然后基于此建立多层索引节点实现的,但在实际的代码实现上,这种结构不好表述,所以要打破既有惯性思维,然后才能好理解Redis中的实现,实际上每个节点除了存储节点自身数据外,还通过level数组保存该节点在整个跳表各个索引层的节点引用。

至此,本次分享就结束了,后期会慢慢补充。

以上仅为个人观点,不一定准确,能帮到各位那是最好的。

好啦,到这里本文就结束了,喜欢的话就来个三连击吧。

扫码关注公众号,获取更多优质内容。

Go面试看这里了~(二十五) 

上一篇:Android应用与多CPU架构


下一篇:一线互联网技术总监的忠告:我们精通那么多技术为何还是做不好一个项目?