专题：数据结构 -- IT技术博客大学习 -- 共学习共进步！

这篇文章是stackoverflow的一篇帖子。上面提到了很多有用的数据结构。有的听过了，经常用，有的没有听过，记录下来。

redis 是 key-value 存储系统，其中 key 类型一般为字符串，而 value 类型则为 redis 对象(redis object)。redis 对象可以绑定各种类型的数据，譬如 string、list 和 set。

在 redis 中，list 有两种存储方式：双链表(LinkedList)和压缩双链表(ziplist)。双链表即普通数据结构中遇到的，在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表，压缩双链表节省前驱和后驱指针的空间(8B)，这在小的 list 上，压缩效率是非常明显的；压缩双链表在 ziplist.h 和 ziplist.c 中实现。

深入剖析 redis 数据结构 dict

在 redis 中有多个数据集，数据集采用的数据结构是哈希表，用以存储键值对。默认所有的客户端都是使用第一个数据集，如果客户端有需要可以使用 select 命令来选择不同的数据集。redis 在初始化服务器的时候就会初始化所有的数据集.。。。。。

深入剖析 redis 数据结构 skiplist

redis 中 zset 是一个有序非线性的数据结构,它底层核心的数据结构是跳表. 跳表(skiplist)是一个特俗的链表，相比一般的链表，有更高的查找效率，其效率可比拟于二叉查找树。

爱喝啤酒的程序员是如何学习数据结构的

下面这几幅图描绘的是一个爱喝啤酒的程序员是如何学习数据结构的，你可以看出，他酒喝了，数据结构也掌握了。

数据结构之treap

treap 是一个很有意思的数据结构，从名字也能看得出来，它是 tree 和 heap 的混合产物。为什么会有这么一个数据结构还得从二叉树(BST)说起。我们都知道，普通的二叉树是不平衡的，在某些情况下进行插入删除操作可以导致时间复杂度从 O(logN) 下降到 O(N)。为了解决平衡的问题，有很多新的二叉树被引入，比如大家熟知的一些：Linux 内核中 CFS 使用到的红黑树(Red-black tree)，数据结构课上都会讲到的 AVL 树。这些树都因为要进行复杂的旋转操作而不容易实现。那么有没有一个实现容易的平衡二叉树呢？Treap 就是一个。普通的二叉树节点只有 key，而 treap 又多了一个 priority，这里的 priority 就是 heap (优先队列)中的 priority。这样， treap 既可以利用二叉树的特性，又可以利用 heap 的特性了。

开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现

在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix(Radix)树实现了这个算法，下面是一些背景知识：首先是Trie树，下图是Wiki http://en.wikipedia.org/wiki/Trie 之中的一个例子 Trie树，尤其是二叉Trie树属于：是一直被使用，从未被(教科书)重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小

开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList

List是工程师的基本功，这里并不描述list增删这些细节的内容，仅仅根据我的理解写一下工程中List库的设计和实践考量。看过几个不同的list库的实现，基本上涉及到如下的设计考量： 1.List数据结构上的差异有没有头结点，是否循环，是否双向。这样就有多种组合，不罗嗦。 2.list的读写的保护。 3.List直接指针遍历还是仿照STL的Iterator方式遍历。 4.List同实际用户数据是采取一体式还是干湿分离式。 5.系统对于数据结构和算法的影响 1.从数据结构上将，Linux Kernel之中的List是双向无头节点链表。空链表如下：非空链表如下：我觉得维护头结点的理由之一就是可以存放list size，而无需用户在应用部分进行维护。如果没有list size，用户需要在List删减的结束的时候维护list size，如果不愿意如此麻烦，只能悲催的在需要读取

开源世界中的算法与数据结构 2 -- Linux Skbuff实现

兼回忆贴，大概在03年开始接触Linux的协议栈代码，那个时候还找不到什么参考书，有些东西自己搞明白了但是也从来没想过在那个论坛发个帖子什么的，也没有现在的记录总结的习惯. 后来有一本08年版的《TCP/IP Architecture, Design and Implementation in Linux》其中解析了Linux2.4 协议栈的多数代码，其中第五章专门涉及skbuff的代码实现讲解，非常详细，这个小短文不翻译整个章节，各种网文很多，只是想根据关键部分说一下我理解的设计背后的原因。 skbuff的形态1 上面是最基本的一个sk_buff了，一个TCP报文的skbuff示意图，这里隐含着一些内容：报文分析的标准模式 skbuff采用的大块控制结构对象指向数据区是标准的实现模式，例如BSD这样的OS以及工程实现中都是这样的。参数的集中与其提供多个对象或者多个参数保存

开源世界中的算法与数据结构 1 -- Linux FIB实现

在Linux2.4的时候，对于Linux的FIB表有些研究。凭着残存的记忆和code，恢复一下FIB的数据结构。首先扫盲一下几个路由协议架构相关的概念：上图为路由协议的基本架构，相关内容在Cisco出版社出版的某一本图书上有概念描述，大概是《Routing TCP》。 1．每个路由协议根据自己收集到的路由信息产生内部的路由表。所有的路由协议的路由信息汇聚到统一的RIB之中。 2． RIB的管理模块根据RIB之中的路由条目按照优先级优选出实际用于转发的路由下发到FIB之中。 3．最终在Packet到来的时候，系统查找FIB表做路由查找。对于FIB的主要需求有两个： 1. 组织和存储选出的路由表项。 2. 按照LPM(最长掩码匹配)算法提供路由检索接口。下图是Linux24之中的FIB表中几个主要的数据对象的数据结构关系。具体字段不做解释，最终的目的就是找到dn_fib_n

stream.js ：一个新的JavaScript数据结构

最近在网上看到了一个新的Javascript小程序――Streams，起初以为是一个普通的Javascript类库，但读了关于它的介绍后，我发现，这不是一个简单的类库，而且作者的重点也不是这个类库的功能，而是――借用文中的一段话：如果你愿意花10分钟的时间来阅读这篇文章，你对编程的认识有可能会被完全的改变(除非你有函数式编程的经验！)。还有： Streams 实际上不是一个新的想法。很多的函数式的编程语言都支持这种特征。

浅谈MySQL索引背后的数据结构及算法

本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

分布式系统的数据结构

常用的数据结构包括：数组，队列，堆栈，链表，树（平衡二叉树，B树，Trie树，堆），哈希表，图，后缀数组，等等。其中，堆，图结构，Trie树及后缀数组解决特定问题，其它数据结构解决通用的查找，更新，删除操作。查找，更新和删除操作一般是O(1)，O(logN)或者O(N)，通用的数据结果大致可分为如下三种： 1, 极端型；某些操作的算法复杂度为O(1)，另外一些算法复杂度为O(N)，比如有序链表查找复杂度为O(N)，更新和删除为O(1)； 2,...