月度归档：5月 2012

B- 树和B+-树

Posted on by
回复

B- 树和B+-树是重要的两个用于数据检索的数据结构，广泛用在文件系统、数据库和数据检索中。

【重申】没有“B’减’树”这样的树，在之前的’-‘ 是个横杠杠

B- 树

类似于二分查找树。但不同于二分查找树，B 树可以有多个孩子节点，这样树的深度就不会太深，其次B 树是平衡树，即所有叶子节点到根节点路径长度一样，所有非叶子节点的孩子节点都满足一定条件（不少于$\lceil m/2 \rceil$、不多于m，m 为阶数），这样查找一个节点就不会便利太深。对B 树有这样的限制：

  1. 非叶子节点有至少$\lceil m/2 \rceil$ 个、至多m 个子节点
  2. 根节点可以至少有两个节点
  3. 所有叶子节点在同一层
  4. 有k 个子节点的非根节点恰好包含k-1 个关键码（key）

满足上面四个要求的树就是B 树。下图是一个m=5阶B 树例子，每个节点最少$\lceil 4/2 \rceil=3$个、最多5 个节点（指针）。关键码是用于区分左右子树（左边子树关键码都比该节点小，右边子树关键码都比该节点大），且非叶子节点和叶子节点关键码内都包含了关键码对应的数据信息（这点和B+ 树不同）。当插入和删除时会发生树的合并和拆分，具体参考【B树 和B+ 树】【性能分析】【动态动画演示】。

400px-B-tree.svg

B 树内没有重复的关键码，且把关键码相近的放在一起，利用了访问的局部性原理。根据第一点B 树有一定比率的非叶子节点是满的（>50%，B* 树可保证>75%），这样就能够提高空间利用率，减少检索和更新磁盘读取次数。但B- 树也有自己的问题：

  1. 因为非叶子节点上的关键码也包含了对应的信息，所以非叶子节点也会变得比较大，影响了阶数m 的扩展
  2. 当需要获取全部或者某个区段的关键码对应的信息，需要遍历B 树

 

B+-树

B+ 树针对B 树一些性能上的缺陷进行了改进，所以B+ 树在使用上更加广泛，通过性能分析和实际应用发现B+ 树比B 树更优。B+ 结构是这样定义的：

  1. 每个节点（除了根节点）至少有$\lceil m/2 \rceil$ 个、至多m 个子节点（同B 树）
  2. 根节点至少有两个子节点
  3. 有k 个子节点的节点必有k 个关键码
  4. 每个叶子节点都有指向下一个叶子节点的指针

从结构上看B+ 树减少了一个指向叶子节点的指针，B 树中关键码是左右子树的划分，不与子节点的某个关键码相同，而在B+ 树中关键码可以与右子树最小的关键码相同，这是因为B+ 树中只有非叶子节点才真正保存关键码对应的信息，而非叶子节点只是用来划分叶子节点和保存叶子节点关键码索引而已。这样非叶子节点就变得非常简单阶数m 也可以取得比较大（类似于文件系统中的inode，如果inode 中也保存了一些数据块的话就会变得很大，每次访问inode 就变得慢了）。

第二个变化就是如下图在每个叶子节点上都有连接下一个叶子节点的指针，这样就将所有的叶子节点以线性检索链表的方式连接了起来。在范围查询和做检查点或者备份时会更快。

800px-Bplustree

 

如果你觉得讲的太简单了，可以参考这里，没见过比那讲的更详细的了！但我个人感觉自己理解了就OK 了，总不至于要自己去写一个B 树的算法~

如何开发一个chrome 插件

Posted on by
回复

一、新建一个空文件夹，创建manifest.json 文件

新建文件夹名字是应用的名称，manifest.json 是应用的一些信息，我们以插件scholarsea为例，文件夹名为scholarsea，对应的的manifest.json 如下所示，具体内容参考chrome 扩展文档。 

   1: {

   2: "name": "Google Scholar \u641c\u7d22",

   3: "version": "0.1",

   4: "description": "use Google Scholar to find the paper you selected",

   5: "icons": { "48": "4848.png" }, 

   6: "page_action": { "default_icon": "1919.png" },

   7: "background_page": "background.html",

   8: "permissions": [ "contextMenus","tabs" ],

   9: "background_page":"background.html"

  10: }

 

二、为你的应用找一个好看的图标

在文件夹下放你的图标，和manifest 中属性相同。我是的19×19 和48×48 大小的png，还不错吧！自己PS的哦

  1919这个是右键时显示的图标   4848这个是插件介绍用

 

三、新建一个html 文件和manifest 中html 属性一致

内容很简单包含一个后面要用的js 文件，这个js 文件名可以随意

   1: <script src="js.js"></script>

 

四、新建js 文件

这里js 文件名和上面html 内js 文件名一致，用于执行插件的核心工作。scholarsea 将所选的文字作为关键字在Google scholar 进行搜索。内容如下：

   1: //open new tab to search

   2: function searchdblp(info,tab){

   3:     var url="http://scholar.google.com/scholar?hl=en&q=

   4: "+info.selectionText+"&btnG=&hl=en&as_sdt=0%2C5"

   5:     window.open(url);

   6: }

   7:  

   8: //add right button click

   9: var menutitle="Google Scholar \u5e2e\u4f60\u641c"

  10: var parent= chrome.contextMenus.create({"title": menutitle,

  11: "contexts":["selection"],"onclick":searchdblp,});

chrome.contextMenus.create 在浏览器邮件添加一个选项，名称为“Google Scholar 帮你搜”，当点击后调用函数searchdblp ，info.selectionText 是我们在浏览器所选的内容。

 

五、发布插件

看看我们这个名为scholarsea 的文件夹下有了哪些内容：

image

最后只需要在chrome 中发布即可，在chrome 的菜单中选择“工具/扩展程序”，然后打包扩展程序即可。这样会生成一个crx 类型的插件安装文件，和一个pem 的密钥文件（用于管理你的插件）。因为所有插件都是源码开放的，需要确认这个插件是你所有的只有这个密钥了。

 

六、一点注意

在上面没有提到重要一点是manifest 和js 内都不支持中文，采用的是unicode 编码，如果你需要写中文的话，请用unicode 编码，有个简单的中文转unicode 的编码方法，如果你装了python 的话就好办了，看看我怎么解决的

   1: >>> u"帮我搜"

   2: u'\u5e2e\u6211\u641c'

   3: >>> u"搜索此人"

   4: u'\u641c\u7d22\u6b64\u4eba'

看到了吧，很方便哦~~

最后提供两个插件，用于搜索作者的文章dblpsea，和google scholar 搜索文章的插件：

【dblpsea】  【scholarsea】

一致性哈希和分布式哈希表

Posted on by
回复

一致性哈希（consistent hashing）和分布式哈希表（DHT: Distributed Hash Table）在最近的学习中经常用到，但是两个概念经常纠缠在一起，不容易分清楚。有时候就不明白这里为什么说的是consistent hashing，而不是用DHT。

从字面的意思来区分：consistent hashing 是一种满足特殊需求的哈希；DHT 是通过哈希实现的分布式的表，归根到底是一个分布式系统。consistent hashing 是理论上节点变化最少数据迁移的哈希方法，而DHT 在实现上更加具体，DHT 把传统的单个K-V 表在分布式多个节点中进行划分，既可以采用consistent hashing 实现，也可以采用其他哈希方法。

继续阅读 →

批量下载同类型文件脚本

Posted on by
回复

有时候想将整个会议的论文下载下来，手动太麻烦，应该浏览器插件完成的，没有去搜，写了个python 脚本来解决。 将url 页面的指定类型文件下载下来！

红玫瑰格式：python xx.py url file_type

参数一：url 地址；参数二：文件类型

   1: #!/usr/bin/env python

   2: #encoding=utf-8

   3:  

   4: import urllib, urllib2

   5: import re

   6: import os,sys

   7:  

   8: def get_files(ourl,file_type):

   9:     print "The URL is "+ourl

  10:     print "The File Type is "+file_type

  11:     path="E:\\temp\\"

  12:     if os.path.exists(path):

  13:         pass

  14:     else:

  15:         os.mkdir(path)

  16:     print "accessing "+ourl

  17:     print "===>>>href<<<==="

  18:     tempstr='href=\"(\S{3,50}\.'+file_type+'\w{0,2})\"'

  19:     htmldata=urllib2.urlopen(ourl).read()

  20:     fileslist=re.findall(tempstr,htmldata)

  21:     if len(fileslist)==0:

  22:         print "no"+" ."+file_type+" files"

  23:     else:

  24:         for app in fileslist:

  25:             if (ourl[-1]=='/'):

  26:                 pass

  27:             else:

  28:                 ourl=ourl[:ourl.rindex("/")+1]

  29:             if (app[0:7]=='http://'):

  30:                 url=app

  31:             else:

  32:                 url=ourl+app

  33:             filedata=app

  34:             try:

  35:                 print url+"\tdownloading ......"

  36:                 filedata=urllib2.urlopen(url).read()

  37:                 print "read "+url

  38:                 filestr=path+url[url.rindex("/")+1:]

  39:                 print "file is "+filestr

  40:                 fp=open(filestr,'wb')

  41:                 fp.write(filedata)

  42:                 fp.close()            

  43:             except: 

  44:                 print "cann't get "+url

  45:     print "===>>>src<<<==="                

  46:     tempstr='src=\"(\S{3,50}\.'+file_type+'\w{0,2})\"'

  47:     htmldata=urllib2.urlopen(ourl).read()

  48:     fileslist=re.findall(tempstr,htmldata)

  49:     if len(fileslist)==0:

  50:         print "no"+" ."+file_type+" files"

  51:     else:

  52:         for app in fileslist:

  53:             if (app[0:7]=='http://'):

  54:                 url=app

  55:             else:

  56:                 url=ourl+app

  57:             filedata=app

  58:             try:

  59:                 print url+"\tdownloading ......"

  60:                 filedata=urllib2.urlopen(url).read()

  61:                 print "read "+url

  62:                 filestr=path+url[url.rindex("/")+1:]

  63:                 print "file is "+filestr

  64:                 fp=open(filestr,'wb')

  65:                 fp.write(filedata)

  66:                 fp.close()            

  67:             except: 

  68:                 print "cann't get >> "+url    

  69:  

  70: if __name__ == "__main__":

  71:     ourl=sys.argv[1];

  72:     file_type=sys.argv[2];

  73:     get_files(ourl,file_type)

MSST 2012

Posted on by
1

IEEE Conference on Massive Data Storage (MSST 2012) 4 月 16-20 日。实验室曾老师中一篇short paper。

Flash 1

Parallel Object and Failure

Short Papers 1

Deduplication

Short Papers 2

Flash 2

 

快读paper 的几个技巧（欢迎补充）

  1. 首先看摘要，知道文章大体背景和概述。
  2. 如果Introduction 最后两段如果不是“section 2 将会讲……，section 3 讲……”，那么将会提到文章最核心，最创新的部分。有时候会直接给出“Our contributions/works are：……”
  3. 看conclusion ，看看作者通过自己的idea 和实验得出了什么结论。
  4. 看图表，简单直接知道实验内容。（有时图表和实验内容联系紧密，看图表看不出什么）。
  5. 最后还有时间穿插地瞄瞄Related works 和Our works（如果有的话）。说不定相关工作有你熟悉的内容。
  6. 另外能先看论文的PPT 也是非常好的方法。

Dynamo: Amazon’s highly available key-value store

Posted on by
回复

原文  中文翻译  参考：Kai – An Open Source Implementation of Amazon’s Dynamo

本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇，个人觉得有两个原因：

  1. 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如：DHT（分布式哈希表）、consistent hashing（一致性哈希）、多版本、副本策略和Merkle tree 等。
  2. 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法，并总结了Dynamo 在实现、配置等方面的经验与教训，对后来者非常有借鉴意义。

继续阅读 →