专栏首页roseduan写字的地方使用 Go 语言写一个数据库—4 数据结构

使用 Go 语言写一个数据库—4 数据结构


前面几篇文章,我已经对 rosedb 有了一定的讲解了,如果还没有看前面的内容,请先看一下之前的内容,这样你才能更好的理解本篇文章的内容。

使用 Go 语言写一个数据库—3 数据库操作

使用 Go 语言写一个数据库—2 基本数据操作

使用 Go 语言写一个数据库—1 基本结构

这一节我会给大家分享我的开源项目当中所涉及到的一些数据结构,有链表、跳表、哈希表、有序集合,比较硬核的数据结构分析,请一定要看完哦!

视频参考在文章的底部!可以先看下文字内容,辅助理解。


链表

链表应该是大家都很熟悉的数据结构了,它指的是使用指针将一组连续的内存块串联起来的一种结构,如下图:

因为链表的内存块不是连续的,因此在链表中查找数据,需要从头到尾遍历链表,平均时间复杂度是 O(n)。

和它相对应的数据结构是数组,数组占用连续的内存空间,因此可直接根据内存寻址定位元素,随机访问的时间复杂度是 O(1)。

在具体实践当中,其实使用得更多的是双向链表,它不仅有指向下一个内存块的 next 指针,还有指向前一个内存块的 prev 指针。

这样的话,可以双向遍历,在某些情况下,能够减少节点遍历的次数。

哈希表

哈希表基于数组,通过一个哈希函数,将不同的 key 映射为数组的下标,将 value 存储至数组对应的下标处。

由于它基于数组,查找的时间复杂度是 O(1) 的,删除的时候,会直接做一个标记,不会大规模移动数据,因此时间复杂度也是 O(1) 的。

只不过哈希表也有一个缺点,那便是数据是无序的。

哈希表的设计比较复杂,需要考虑到装载因子、哈希函数、扩容、哈希冲突等等,在大多数编程语言中都有了内置的实现,比如 Java 中的 HashMap,Go 语言的 map。

跳表

跳表是针对链表的劣势而进行改进的,我们知道传统的链表查找数据只能从头到尾开始遍历,那么有没有什么办法能够加速这个查询呢?

在原始链表上不太好解决这个问题,因为链表的节点内存地址不是连续的,既然在一维解决不了这个问题,那么我么可以上升到二维。

这也是常见的解决问题的一个思路,一维解决不了的问题,我们会上升到二维,一些常见的数据结构其实都是这个思路,比如二叉树、图。

在原始的链表基础之上,加一层索引,每次查找的时候都从索引层下来,这样不用从原始链表挨个遍历,查找的速度加快了。

这就是跳表的基本思路,通过在原始链表之上,加上一级一级的索引,减少节点遍历的个数。

跳表还有一个优势,那就是链表节点的数据是有序排列的,这样很容易就能够实现区间查找、前缀扫描、排名统计等功能。

有序集合

有序集合是一个组合的数据结构,使用跳表 + 哈希表,其中跳表主要是保证节点有序,这一点在前面已经说过了,而哈希表则提供了O(1)的访问性能,有序集合的结构如下图:

有序集合节点由一个哈希表 dict 和一个跳表 skipList 组成,dict 的 key 是 member,value 是一个跳表节点。而 skipList 则存储的是 score 和 member 信息。

参考视频


题图:from wallheaven.cc

本文分享自微信公众号 - roseduan写字的地方(rose_duan),作者:roseduan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用 Go 语言写一个数据库—3 数据库操作

    在前面的两篇文章当中,我给大家介绍了 rosedb 的基础结构,以及基本的数据操作流程。

    roseduan
  • 使用 Go 语言写一个数据库—6 完结撒花

    Hello 大家好,我是 roseduan,前面的几篇文章,我已经讲述了 rosedb 最基础也是最核心的知识,如果你没有印象的话,可以温习一下:

    roseduan
  • 使用 Go 语言写一个数据库—2 基本数据操作

    上一次给大家介绍了 rosedb 的基本结构:使用 Go 语言写一个数据库—1 基本结构

    roseduan
  • 使用 Go 语言写一个数据库—5 命令行

    Hello 大家好,我是 roseduan,上一次给大家分享了 rosedb 项目当中所涉及到的一些数据结构,有链表、哈希表、跳表、有序集合,内容比较的硬核,你...

    roseduan
  • Go语言基础4 - 数据(基本数据结构)

    new 函数格式为: new(T) 特点:它返回一个指针, 该指针指向新分配的,类型为 T 的零值

    zhangyunfeiVir
  • Go语言读写数据库

    我用的驱动是:https://github.com/Go-SQL-Driver/MySQL 理由跟 https://github.com/astaxie/bui...

    李海彬
  • Go语言读写数据库

    我用的驱动是:https://github.com/Go-SQL-Driver/MySQL 理由跟 https://github.com/astaxie/bui...

    李海彬
  • 一个 Go 语言实现的数据库

    rosedb 是一个稳定、高性能、快速、内嵌的 k-v 数据库,支持多种数据结构,包含 String、List、Hash、Set、Sorted Set,接口名称...

    逆锋起笔
  • R语言数据结构一

    R是面向对象的语言,它跟其他编程语言的数据类型差不多,有四种,分别为:数值型,复数型,逻辑性和字符型

    呆呆
  • go语言数据结构 环形队列

    队列是一种常用的数据结构,这种结构保证了数据是按照“先进先出”的原则进行操作的,即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构,保证了元素也是...

    李海彬
  • Go语言经典库使用分析(八)| 变量数据结构调试利器 go-spew

    我们在使用Golang(Go语言)开发的过程中,会通过经常通过调试的方式查找问题的原因,解决问题,尤其是当遇到一个很棘手的问题的时候,就需要知道一段代码在执行的...

    飞雪无情
  • 为什么数据库常使用有序数据结构而编程语言使用哈希表结构

    在编程语言里哈希表结构(例如 Go 中的 Map,Python 中的 Dict,Java 中的 HashMap 等)要比有序索引的数据结构(例如Tree)更常见...

    哒呵呵
  • 标准库 collections 中 4 个常用的数据结构

    collections 库是标准库的一部分,里面有很多数据结构,在列表、字典、元组的基础上做了很多修改和提升。

    somenzz
  • 使用Go语言访问JSON数据(gojsonq)

    Query select * from vendor.items where price > 1200 or id null 使用 gojsonq的方式查询

    程序员同行者
  • Go 语言—数据结构和算法项目推荐

    今天分享的是一些数据结构和算法的项目,在我自己学习 Go 语言的时候,在掌握基础的语法知识之后,会针对性的刷一些 leetcode 题目,借此来巩固自己的语法知...

    roseduan
  • golang学习之旅:使用go语言操作mysql数据库

    1.下载并导入数据库驱动包 官方不提供实现,先下载第三方的实现,点击这里查看各种各样的实现版本。 这里选择了Go-MySQL-Driver这个实现。地址是:ht...

    李海彬
  • 【实践】GO语言框架REDIGO使用REDIS数据库入门

    基于GO的REDIOS调用框架有开源库redigo。本文主要讲解redigo的框架和调用样例。

    辉哥
  • 用 Python 写一个 NoSQL 数据库

    本文译自 What is a NoSQL Database? Learn By Writing One In Python. 完整的示例代码已经放到了 Git...

    小小科
  • 用 Python 写一个 NoSQL 数据库

    本文译自 What is a NoSQL Database? Learn By Writing One In Python.

    用户1558438

扫码关注云+社区

领取腾讯云代金券