使用 Go 语言写一个数据库—4 数据结构
使用 Go 语言写一个数据库—4 数据结构
前面几篇文章，我已经对 rosedb 有了一定的讲解了，如果还没有看前面的内容，请先看一下之前的内容，这样你才能更好的理解本篇文章的内容。
这一节我会给大家分享我的开源项目当中所涉及到的一些数据结构，有链表、跳表、哈希表、有序集合，比较硬核的数据结构分析，请一定要看完哦！
视频参考在文章的底部！可以先看下文字内容，辅助理解。
链表
链表应该是大家都很熟悉的数据结构了，它指的是使用指针将一组连续的内存块串联起来的一种结构，如下图：
因为链表的内存块不是连续的，因此在链表中查找数据，需要从头到尾遍历链表，平均时间复杂度是 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