​1972 年 R. Bayer 和 E. McCreight 的论文（参考资料 [1]）提出了 B- 树。B- 树是一棵平衡树，与一般的平衡二叉树（AVL，红黑树等）不同的是，B- 树的每个节点最多可以拥有 m（m>=2）个元素，（m+1）个子节点，并且所有的叶子节点位于同一层。B- 树的查找和插入的时间复杂度和二叉树一样，都是 O(logn)，但因为每个节点保存的元素比较多（一般是几十个到几百个之间），树的高度比一般的二叉树要小很多，访问硬盘次数更少，在数据不能全部加载到内存的时候比一般的二叉树效率要好。

    ​脚本的最初原型是当年用fvwm的时候为了山寨一个生成家目录下的树形结构菜单写的一个广度优先遍历；后来在把文件系统从ext3转到ext4的时候重新分区，把文件备份到windows上，结果还原回来的时候权限都乱了，于是把queue整理了一下写成一个单独的脚本用来改权限；后来还实现了一个深度优先遍历的版本。今天把这两个函数都整理一下。一般来说简单的操作用find+各种工具就行了，除非是对遍历顺序有要求或操作比较复杂。

    Pipes是hadoop提供的c++接口，但是在官网上找不到pipes的文档，只能从例子开始一点点摸索。实验环境是debian 6 amd64，hadoop 1.0.3。hadoop的安装目录是$HOME/hadoop，安装和配置过程在上一篇安装笔记中有提到。

    记录一下hadoop集群的搭建过程，一共3台机器，操作系统都是debian 6，hadoop版本是1.0.3，jre是源里的openjdk-6。hadoop官网的说明挺详细，就是不能快速搭建出一个能跑的环境。在网上找到一篇文章(见参考资料[1])，虽然文章中用的是0.20版本，但是在1.0.3上也适用。这里使用master，slave1和slave2分别作为三台机器的主机名。为了操作方便，每台机器上都有一个用户hadoop，密码都一样。以下的配置操作都在master上进行。