作者:July,chx/@罗勍出处:结构之法算法之道blog导读 本文重点谈了4个东西,LSM-Tree及COLA-Tree,及StackOverflow及OSQA,全文分为以下两部分:第一部分从最基本的LSM-Tree的C0C1两组件算法,谈到多组件算法( LSM-Tree最适用于那些索引插入频率远大于查询频率的情况,比如,对于历史记录表和日志文件来说,就属于这种情况),再稍稍提下COLA-tree,让读者对COLA有个印象。第二部分则是讲讲最近我和几个朋友利用OSQA(OSQA为仿照StackOverflow的开源系统)搭建的一个仿照StackOverflow的问答系统,分享实践开发过程中遇到的一些问题及其解决方式,此部分主要由chx/@罗勍编写。 至于上提到
发布时间:
2014-04-14 |
类别:
技术文章 | 阅读:278929 | 评论:0 |
标签:
数据结构
五竹,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
发布时间:
2011-03-24 |
类别:
技术文章 | 阅读:202567 | 评论:2 |
标签:
数据结构