作者：July，chx/@罗勍出处：结构之法算法之道blog导读    本文重点谈了4个东西，LSM-Tree及COLA-Tree，及StackOverflow及OSQA，全文分为以下两部分：第一部分从最基本的LSM-Tree的C0C1两组件算法，谈到多组件算法( LSM-Tree最适用于那些索引插入频率远大于查询频率的情况，比如，对于历史记录表和日志文件来说，就属于这种情况)，再稍稍提下COLA-tree，让读者对COLA有个印象。第二部分则是讲讲最近我和几个朋友利用OSQA(OSQA为仿照StackOverflow的开源系统)搭建的一个仿照StackOverflow的问答系统，分享实践开发过程中遇到的一些问题及其解决方式，此部分主要由chx/@罗勍编写。  至于上提到

五竹,20110418Redis: A persistent key-value database with built-in net interface written in ANSI-C for Posix systems1 Redis 内存存储结构本文是基于 Redis-v2.2.4 版本进行分析.1.1 Redis 内存存储总体结构Redis 是支持多key-value数据库(表)的,并用 RedisDb 来表示一个key-value数据库(表). redisServer 中有一个 redisDb *db; 成员变量, RedisServer 在初始化时,会根据配置文件的 db 数量来创建一个 redisDb 数组. 客户端在连接后,通过 SELECT 指令来选择一个 reidsDb,如

导读： 　　linux内核中的用户态地址空间管理使用了红黑树(red-black tree)这种数据结构，我想一定有许多人在这种数据结构上感到困惑，我也曾经为此查阅了许多资料以便了解红黑树的原理。最近我在一个外国网站上看到一篇 讲解红黑树的文章，觉得相当不错，不敢独享，于是翻译成中文供所有内核版的弟兄们参考。由于本人水平有限，难免有出错之处，欢迎大家指正。 　　原文网址：http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html 　　 　　加两个链结地址: 　　红黑树的实地使用 　 　 http://www.linuxforum.net/forum/show

B树即二叉搜索树：       1.所有非叶子结点至多拥有两个儿子（Left和Right）；       2.所有结点存储一个关键字；       3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；如： B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼

哈希表（Hashtable）又称为“散置”，Hashtable是会根据索引键的哈希程序代码组织成的索引键（Key）和值（Value）配对的集合。Hashtable 对象是由包含集合中元素的哈希桶（Bucket）所组成的。而Bucket是Hashtable内元素的虚拟子群组，可以让大部分集合中的搜寻和获取工作更容易、更快速。  哈希函数（Hash Function）为根据索引键来返回数值哈希程序代码的算法。索引键（Key）是被存储对象的某些属性值（Value）。当对象加入至 Hashtable时，它存储在与对象哈希程序代码相符的哈希程序代码相关的Bucket中。当在Hashtable内搜寻值时，哈希程序代码会为该值产生，并且会搜寻与该哈希程序代码相关的Bucket。例如，student和tea

　　这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引(Secondary key)在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：　　同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。　　MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。　　InnoDB索引

一、栈： 1、后缀表达式的求值； 2、中缀到后缀表达式的转换； 3、深度优先搜索的非递归实现； 4、动态规划的优化：用于维护一个凸序列，便于二分查找，如LIS问题的O(nlgn)算法。 二、队列： 1、树的层序遍历； 2、广度优先搜索； 3、Bellman-Ford算法的SPFA实现； 4、网络流中FF算法的Edmonds-Karp实现，以及Preflow算法的队列优化实现。 三、二叉搜索树： 1、对大量的关键字的索引查找； 2、有很多平衡策略以改善其平均性能： 常用平衡树：AVL，红黑树，随机化BST，Splay Tree，Treap（或叫笛卡儿树）。 四、散列表（has