pdf 地址

涉及主题

  • I/O model and cache-oblivious analysis.
  • Write-optimized data structures.
  • How write-optimized data structures can help file systems.
  • Block-replacement algorithms.
  • Indexing strategies.
  • Log-structured merge trees.
  • Bloom filters.

# Module 1: I/O Model and Cache-Oblivious Analysis

IO模型与缓存无关分析

# Module 2: Write-Optimized Data Structures

写优化的数据结构

# 二叉查找树(BST、二叉排序树)

  1. 左子树上的所有结点的值都小于根结点的值
  2. 右子树上的所有结点的值都大于根结点的值
  3. 左右子树都是二叉树

二叉查找树的查询效率平均是 O(logN),最差效率是 O(N)

         1
        / \
       2   5
          /    
         6
1
2
3
4
5
   1
    \
     2
      \
       5
        \
         6
1
2
3
4
5
6
7

上图两种情况下,第一种是我们期望的一般情况,第二种是退化到链表的特殊情况,有最差效率

用平衡二叉树解决这个问题

# 平衡二叉树(AVL Tree)

在二叉查找树之外还有以下规则

  1. 可以是一颗空树
  2. 左子树和右子树高度差不大于1
  3. 子树也是平衡二叉树

平衡二叉树通过“旋转”这个神奇的操作来保证这点的

    1
     \
      2
       \
        5
1
2
3
4
5

这种状态的树已经不满足平衡二叉树的定义了,需要旋转,结果是

    2
   / \
  1   5
1
2
3

平衡二叉树的旋转一共有四种情形,注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。

  1. LL型

    平衡二叉树某一节点的左孩子的左子树上插入一个新的节点,使得该节点不再平衡。这时只需要把树向右旋转一次即可,如图所示,原A的左孩子B变为父结点,A变为其右孩子,而原B的右子树变为A的左子树,注意旋转之后Brh是A的左子树(图上忘在A于Brh之间标实线)

  2. RR型

    平衡二叉树某一节点的右孩子的右子树上插入一个新的节点,使得该节点不再平衡。这时只需要把树向左旋转一次即可,如图所示,原A右孩子B变为父结点,A变为其左孩子,而原B的左子树Blh将变为A的右子树。

  3. LR型

    平衡二叉树某一节点的左孩子的右子树上插入一个新的节点,使得该节点不再平衡。这时需要旋转两次,仅一次的旋转是不能够使二叉树再次平衡。如图所示,在B节点按照RR型向左旋转一次之后,二叉树在A节点仍然不能保持平衡,这时还需要再向右旋转一次。

  4. RL型

    平衡二叉树某一节点的右孩子的左子树上插入一个新的节点,使得该节点不再平衡。同样,这时需要旋转两次,旋转方向刚好同LR型相反。

# Module 3: (Case Study) TokuFS--How to Make a Write-Optimized File System

(案例学习)TokuFS —— 怎样做一个写优化的文件系统

# Module 4: Paging

分页

# Module 5: What to Index

对什么建立索引

# Module 6: Log Structured Merge Trees

LST树

# Module 7: Bloom Filters

布隆过滤器