Index

索引是一种数据结构，支持高效检索&动态调整（数据库技术）。

• 主码（Primary Key）：每条记录的唯一标识。

• 辅码：可重复的属性

• 索引：把关键码与它对应的记录未知关联起来的过程（关键码，指针）

  • 稠密索引：每个记录建立一个索引项。

    主文件无需按照关键码排序。

  • 稀疏索引：一组记录建立一个索引项。

    主文件必须按照关键码次序存放。

    可以把记录分块，索引指针指向每块的起始位置。

• 索引文件：记录这种联系的文件。

• 主文件：原始数据记录

  一个主文件可能有多个相关索引文件，每个索引文件支持一个索引字段。

线性检索

按照索引码值的顺序进行排序的文件。

• 特点

  可以访问变长数据库记录，支持高效二分检索。

  体积太大，只能存储在磁盘中，影响效率。

• 二级线性索引

  一个磁盘可以存放M个记录。

  原始数据有N个记录，一级索引也有N个记录，则一级索引占用\(N/M\)个磁盘块。

  再对一级索引按照磁盘块建立二级索引，只需要\(N/M^2\)个磁盘块。

  每个二级索引存放对应的一级索引块中的第一个索引。

  检索过程使用两次二分搜索即可。

• 假定一个计算机系统有4096字节的磁盘块，每个磁盘的磁盘号可以用一个4字节的整数表示。要存储的每一条记录中4个字节是关键码，64个字节是数据字段。记录已经排序，顺序地存储在磁盘文件中。我们建立一个稠密索引，该线性索引的结构为：（每个文件磁盘块的最小关键码，该块磁盘的磁盘号），通过线性索引访问磁盘文件中的记录。

• 如果线性索引的大小是2MB。最多可以在磁盘文件中存储 15M 条记录。

  2MB/8B * (4096B/68B) = 0.25M * 60 = 15M

• 如果线性索引也存储在磁盘中（这样它的大小仅受二级索引的限制），而且使用4096个字节的二级索引，二级索引中的每个单元引用线性索引的磁盘块中最小的关键码值。文件中最多可以存储 15M 条记录。

  4096/8 (二级索引个数) * 4096/8 (每个二级索引指向一个存一级索引的块，每个块中一级索引的个数) * 4096/68 (每个一级索引指向一个块，每个块存放记录的个数) = 2^18 * 60 = 15M

静态检索(Deprecated)

文件创建完成时索引就不能再被修改了。

几乎没有插入/删除，或者允许定期重新组织结构的话，效率还是很高的。

倒排检索

由属性值来确定记录的位置，称为倒排检索（基于属性/基于正文）。

• 基于属性的倒排

  倒排表：(attr, ptrList)

  ​ 属性（不唯一） --> 若干记录指针（唯一，如关键码或主文件地址）

  ​ 可以对不同属性建立多个倒排表。

  优点：基于属性的高效检索。

  缺点：倒排表空间代价，更新运算效率降低。

• 对正文文件的倒排

  支持文本内容的快速检索

  • 词索引

    提取关键词（过滤停用词），对关键词建立倒排表：

    (keyword, [(text, position), ...])

    检索时，首先检索关键词，之后提取关键词对应的记录指针列表，获取记录。

    通常用另一个索引结构对关键词进行检索，如Trie图，散列。

  • 全文索引

  优点：高效检索文本数据库。

  缺点：支持的检索类型有限，检索词有限，空间代价极高。

动态检索

动态更新删除，并保持最佳检索性能。

B树

• 定义

  m阶B树为m路平衡查找树，或者为空，或者：

  • 每个节点至多m个子树（m-1个关键码）
  • 根节点至少2个子树，其他非叶节点至少ceil(m/2)个子树。

• **节点的一般形态 **

  每个节点都存放在一个单独的磁盘块中，所以每读入一个节点需要磁盘IO一次。

  [ P0 K1 P1 K2 P2 ... P(j-1) Kj Pj ]
  

  包含j个递增关键码K，j+1个指向两个关键码之间的子节点的指针。

  注意关键码从1开始编号。

• 性质

  • 有k个子树（指针P）的节点有k-1个关键码K
  • 树高平衡，叶节点位于同一层，关键码不重复
  • 父节点关键码是子节点的分界
  • 访问局部性原理：值相近的记录放在相近的磁盘页中。
  • 节点关键码至少一定比例是满的（保持效率）

• 查找

  • 两步交替

    • 读取根节点，在其K个关键码中检索目标关键码T。找到则检索结束。
    • 否则，T落在两个K之间，取对应的P子树继续检索。如果P为空指针，检索失败。

  • 检索长度

    H为树高，则最多H次读盘上的节点。

    考虑找到后要再读取主数据，则最多需要访外H+1次。

• 插入

  保持等高（尽量）、等阶的性质。

  找到最底层合适位置插入，溢出则节点分裂为左右两个节点，中间关键码连同新指针提升进入父节点，直到不溢出（根节点也溢出时，树高增加一层）。

  节点分裂：插入后若节点数为m（溢出），则

  [K1 K2 ... Km] -> [K1 ... K(ceil(m/2)-1)] + 
                  [K(ceil(m/2))] + 
                  [K(ceil(m/2)+1) ... Km]
  

  查找：失败需要读盘H次。

  插入：不分裂需要1次写盘，分裂的最后一个节点需要3次写盘，分裂中间的节点需要2次写盘。

  故插入最多IO次数为：\(H+3+(H-1)*2 = 3H+1\)

• 删除

  • 叶节点

    • 删除后节点数不小于ceil(m/2)-1：直接删除

    • 删除后节点数小于ceil(m/2)-1

      • 相邻兄弟节点关键码大于ceil(m/2)-1

        借若干关键码，调整父节点（实际结果是把父节点分界拉下来，兄弟的推上去）

      • 相邻兄弟节点关键码等于ceil(m/2)-1

        合并两个节点，并把父节点分界拉下来（有可能使树高减一）

  ## rank = 3
  # ====== init ======
          [55,65]
        /    |    \
     [47] [60,62] [78]
  # ====== delete 78 ====== (borrow from brother)
          [55,62]
        /    |    \
     [47]   [60]   [65]
  

  • 非叶节点

    把此关键码与后继交换位置，成为叶节点再删除。

• 性能分析

  共有N个关键码的B树有N+1个叶节点（外部空指针）。

  证明：设有l个空指针，n个节点，第i节点有x_i个关键码，x总和即关键码总数N，则边的总数m为：

\[ \displaylines{ m = l + m' = l + n - 1 = \sum_{i=1}^n(x_i + 1) = N + n } \]

设树m阶k层（根节点在第0层），则通过另一种方法计算最后一层的节点数，

最大高度公式：（也是最大检索次数）

\[ \displaylines{ N+1 \ge 2*\lceil \frac m 2 \rceil^{k-1} \\ k \le 1 + log_{\lceil m/2 \rceil}(\frac {N+1} 2) \\ } \]

最小高度公式：

\[ \displaylines{ N+1 \le m^k \\ k\ge log_m(N+1) } \]

设p为内部节点数，s为每插入一个关键码的平均分裂节点数：

\[ \displaylines{ s = \frac{p-1}{N-1} \le \frac 1 {\lceil m/2 \rceil - 1} } \]

• 高度为2的5阶B树，所含关键字的个数最少是5。

第一层最多有4个关键字，插入第五个后分裂为两层。

• B树不支持顺序查找。B+树支持顺序查找。

B+有链表，但B树没有这种方便的结构。

• 3阶B树含2047个关键字，则最高11层，最矮7层。

若考虑叶节点也是一层，则最高12层。

B+树

B树变体，只在叶节点存储信息。

MySQL索引采用的就是B+树。

• 定义

  m阶B+树或者为空，或者：

  • 每个节点至多m个子节点
  • 根节点至少2个子节点，非根节点至少ceil(m/2)个子节点，

• 性质

  • 有k个子节点的节点有k个关键码（从1开始编号！）

    [K1 P1 ... Km Pm]
    

    每个Pi指针指向一个子节点，对应的Ki为子节点中关键码的最大值（或最小值）。

  • 叶节点一般用双链表连接起来

• 查找

  读取根节点，二分检索范围，取对应子树继续查找。

  直到查找到叶节点层。

• 插入

  • 分裂：

    [K1 ... Km Km+1] --> [K1 ... K(floor(m/2))] + 
                    [K(ceil(m/2)) ... Km Km+1]
    

    之后提升K(floor(m/2))到父节点，递归检查是否需要分裂。

• 删除

  • 删除关键码后个数大于ceil(m/2)，结束。

  • 删除关键码后个数小于ceil(m/2)：

    • 兄弟可以借节点：借一个，调整父节点中的关键码，结束。

      需要把兄弟的一个关键码与对应子树挪过来，并修改父节点分界。

    • 兄弟也借不了，和兄弟合并。删除一个父节点关键码，递归向上检查父节点关键码数量。

红黑树

定义

满足如下约束的BST树：

• 黑红二色：每个节点被染色为红色或黑色。
• 首尾皆黑：根节点与叶节点（NULL）均为黑色。
• 红红不连：红色节点不相连。
• 黑点同阶：任意节点到其叶节点的路径包含相同数目的黑色节点。

节点X的阶（黑色高度，Rank）：该节点到对应子树的任一外部节点的路径上黑色节点的个数。不包括自身，包括叶节点。叶节点阶0，根节点的阶称为树的阶。

性质

• 满二叉树（扩充二叉树，树叶均为黑色NULL）

• k阶红黑树根到叶的简单路径长度介于[k, 2k]间

  均为黑节点最短，黑红相间最长。此性质限制了树高，允许红黑树在最坏情况下相比普通的BST都是高效的。

• 内部节点数最少是高为k的完全满二叉树，即至少有\(2^k-1\)个内部节点。

• n个内部节点红黑树的最大高度：\(2log_2(n+1)+1\)

  设阶为k，树高为h。

\[ \displaylines{ h \le 2k+1 \\ n \ge 2^k - 1 \\ \Rightarrow h\le 2log_2(n+1)+1 } \]

红黑树之插入

# TL;DR
首先插入目标位置，标记为红色。
* P不存在：变黑。
* P黑色：结束。
* P红色：双红调整。
    * U黑色（eg.P左U右）：
        * X与U同侧（eg.为左子节点）：旋转GP，换色（P变黑，XG变红）。
        * X与U异侧（eg.为右子节点）：旋转PX（退化到上一种情况），旋转GX，换色（X变黑，GP变红）。
        # 换色规律：当前的父节点变黑，两个子节点变红
    * U红色：
        换色（G非根节点时变红；PU变黑），递归向上红红检查。

红黑树本身仍是BST树，插入元素的位置首先根据BST的二分规则找到，一定是某一个NULL叶节点处。

新插入的节点X标记为红色。设父节点P，祖父节点G，叔节点U。

• X无父节点（X是根节点）：换为黑色，结束。

• 父节点P黑色：结束（不破坏红黑树的约束）。

• 父节点P红色：进行双红调整：

  此时已知P为红色，故G为黑色且阶为1。

  • U为黑色：旋转

    由于G阶为1，U只能是NULL叶节点。

    调整方法：以G为轴，旋转P。

    ### BST Rotation
    ### 旋转操作本质上是在**不破坏BST树的二分性质**的情况下转移节点的方法！
    ## Right Rotation
    # axis X, target Y. Note B is transfered.
           \                \
           [X]              [Y]
          /   \            /   \
        [Y]     C   -->   A    [X]
       /   \                  /   \
      A    *B*               *B*   C
    
    ## Left Rotation
    # axis Y, target X. Reversion of Right Rotation.
           \                \
           [X]              [Y]
          /   \            /   \
        [Y]    C    <--   A    [X]
       /   \                  /   \
      A    *B*               *B*   C
    

    ### RB-Tree RR rotation
    ### 以下讨论针对P在左，U在右的情况。P右U左时，两种case要反过来。
    ## X is left child
    # ====== insert X ======
           \
            [G]
           /   \
         (P)    []U
        /   \
      (X)   []
     /  \ 
    []  []
    
    # ====== right rotate G, P ======  
    # Note the color is also changed!
            \
            [P]
           /    \
         (X)     (G)
        /   \   /   \
       []   [] []   []U
    
    ## X is right child
    # ====== insert X ======
           \
            [G]
           /   \
         (P)    []U
        /   \
       []   (X)
            /  \ 
           []  []
    
    # ====== left rotate P, X ====== 
    # degenerate to case [X is left child]
           \
            [G]
           /   \
         (X)    []U
        /   \
      (P)   []
     /  \ 
    []  []
    
    # ===== right rotate G,X ======
            \
            [X]
           /    \
         (P)     (G)
        /   \   /   \
       []   [] []   []U
    

  • U为红色：换色

    G阶为1，故红色U节点下只能挂两个叶节点。

    ### RB-Tree RR change color
    ## for simplicity, we omit [] NULL leaves.
    # ====== insert X ======
          \
          [G]
         /   \
       (P)   (U)
      /
    (X)
    
    # ====== change color ======
    # of G, P, U
          \
          (G)
         /   \
       [P]   [U]
      /
    (X)
    

    如果G是根节点，则不用改变G的颜色。

    否则，由于此时G变为红色，需要递归向上继续进行红红检查。

红黑树之删除

# TL;DR
* X没有空树叶：与后继交换，再删除后继（退化为下两种情况）
* X有一个空树叶：
    删除X，用非空子节点替换，变黑。
* X有两个空树叶：
    * X红色：直接删除X。
    * X黑色：双黑调整。
        * B红色：PB旋转，变色（此处BP换色），退化为下两种情况。
        * B黑色：
            * LR均黑：删除X，B变红，P变黑，递归向上双黑调整。
            * L黑R(N)红：删除X，PB旋转，换色（PN变黑，B变为P的原色）。
            * L(N)黑R红：删除X，BN旋转，PN旋转，换色（PB变黑，N变为P的原色）。
            * LR均红：上两种情况任选其一执行即可。

• 待删节点没有空树叶：

  根据BST规则，先与右子树最小的后继结点交换（换值不换色），再删除该后继（退化到以下两种情况）。

• 待删节点只有一个空树叶：

  首先，待删节点只能是黑色的，且非空的另一个子节点一定是红色节点，该红色节点下只能挂两个叶节点（否则两个子树阶不相等）。删除后把红子节点替换到此处，变黑，结束。

  ## only one case
  # ====== delete X ======
       /
     [X]
    /   \
   []   (Y)     
       /   \
      []   []
  # ====== lift Y, change color ======
       /
     [Y]
    /   \
   []   []     
  

• 待删节点有两个空树叶：

  • 待删节点红色，直接删除。

  • 待删节点黑色，双黑调整（直接删除会使阶失衡）：

    设待删节点为X（双黑节点），父节点P，兄弟节点B。

    • B为红色：

      则P只能为黑色，B的子节点为非空黑色子节点。

      操作：旋转P-B，转化为后两种情况。

      ## delete Condition 1
      # ====== init ======
      # l、r是阶为2的子树, l、r本身是非空**黑**节点。
            \
             P
           /   \
         [X]    (B)
        /  \    /  \
       []  []  l    r
      
      # ====== rotate P, B ======
            \
            (B)
           /   \
          P     r
        /  \
      [X]   l
      
      # ====== change color ======
            \
             B
           /   \
         (P)     r
        /  \
      [X]   l
      
      # since l is a black Brother for X now
      # this question degenerates to the following two cases:
      

    • B为黑色，B的子节点均黑色：

      此时P为红色或黑色。B的两个子节点只能为叶节点。

      ## delete Condition 2
      # ====== init ======
            \
             P
           /   \
         [X]   [B]
        /  \   /  \
       []  [] []  []
      
      # ====== delete X ======
            \
             P
           /   \
          []   [B]
               /  \
              []  []
      
      # ====== change color ======
             \
            [P]
           /   \
          []   (B)
               /  \
              []  []
      

      P原来红色时，调整结束。

      P原来黑色时，由于这一个子树整体少了一阶，需要递归向上双黑调整。

    • B为黑色，B的子节点有至少一个红色：

      分三种情况讨论。

      ### delete Condition 3
      ### for simplicity, omit NULL leaves.
      
      ## only right Nephew is red
      ## so B's left child is black, and thus must be NULL leaf.
      # ====== init ======
            \
             P
           /   \
         [X]   [B]
                  \
                  (N)
      
      # ====== delete X ======
            \
             P
               \
               [B]
                  \
                  (N)
      
      # ====== rotate P,B ======
            \
            [B]
           /   \
          P     (N)
      
      # ====== change color ======
      # here B is changed to the original color of P
            \
             B
           /   \
         [P]    [N]
      
      ## only left Nephew is red
      # ====== init ======
            \
             P
           /   \
         [X]   [B]
              /   
            (N)
      
      # ====== delete X ======
            \
             P
               \
               [B]
              /   
            (N)
      
      # ====== rotate B,N ======
            \
             P
               \
               (N)
                  \
                  [B]
      
      # ====== rotate P,N ======
            \
            (N)
           /   \
          P    [B]
      
      # ====== change color ======
      # here N is changed to the original color of P
            \
             N
           /   \
         [P]    [B]
      
      ## both Nephews are red
      ## do either of the first two methods is OK
      ## for simplicity, we adopt the first method, to work on (R).
      # ====== init ======
            \
             P
           /   \
         [X]   [B]
              /   \
            (L)   (R)
      
      # ====== delete X ======
            \
             P
               \
               [B]
              /   \   
            (L)   (R)
      
      # ====== rotate P,B ======
            \
            [B]
           /   \
          P     (R)
           \
           (L)
      
      # ====== change color ======
            \
             B
           /   \
         [P]    [R]
           \
           (L)
      
      # ====== another possible method ======
      #        \
      #         L
      #       /   \
      #     [P]    [B]
      #              \
      #               (R)
      

红黑树性能

平均和最差检索\(O(lgn)\)。

统计性能优于AVL树。且增删算法相对简单。

set，multiset，map，multimap均为红黑树变体。