红黑树&B树应用及索引原理

算法导论（第三版）学习笔记红黑树 + B树部分

第13章红黑树

二叉搜索树的基本动态集合操作，该二叉搜索树的高度为h
- SEARCH
- PREDECESSOR
- SUCCESSOR
- MINIMUN
- MAXIMUM
- INSERT
- DELETE
以上操作的时间复杂度为O(h)，对于高度较低的二叉搜索树，操作执行较快，但是当树高度较高时，这些集合操作可能并不比链表上执行的要快
红黑树 red-black tree
- 可以保证最坏情况下的基本动态集合操作的时间复杂度为O(lgn)

13.1 红黑树的性质

红黑树是一颗二叉搜索树
每个结点上增加一个存储位来表示结点的颜色 RED BLACK
通过对任何一条从根结点到叶子结点的简单路径上各个结点的颜色进行约束，红黑树确定没有一条路径会比其他路径长出2倍，因而近似平衡
红黑树的每个结点的属性
- color
- key
- left
- right
- p
如果一点结点没有孩子或者父结点，则相应指针属性的值为NIL
- NIL视为指向二叉搜索树叶子结点的指针
- 把带关键字的结点视为树的内部结点
红黑树性质
1. 每个结点或是红色，或者黑色
2. 根节点是黑色的
3. 每个叶子结点（NIL）是黑色
4. 如果一个结点是红色，则它的两个孩子都是黑色
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 一颗红黑树是满足以上5个性质的二叉搜索树
从某个结点出发到达一个叶节点的任意一条简单路径上的黑色结点的数量称为该节点的黑高 black-height
根据性质5，从该节点出发的所有下降到其叶子的简单路径的黑色结点个数都相同；
红黑树的黑高为其根节点的黑高

基础概念回顾，详细学习包括算法导论红黑树的基本动态集合操作学习，和C++红黑树map实现学习；
MARK - PAGE188

第18章 B 树

B树是为磁盘或者其他直接存取的辅助设备而设计的一种平衡搜索树；
类似于红黑树，但是能更好的降低磁盘I/O操作数；
关系型数据库使用B树或者B树的变种来存储信息（MySQL，PGSQL）
B树的结点可以有很多，从数个到数千个，一个B树的“分支因子”可以相当大，依赖于使用的磁盘单元特性
类似于红黑树，每棵树含有n个结点，B树的高度为O(lgn)

一颗B树的严格高度可能比一颗红黑树高度要小的多，因为它的分支因子，也就是表示高度的对数的底数可以非常大；因此，我们可以使用B树在时间O(logn)之内完成动态集合的操作

B树是一种平衡多叉查找树
B树的子节点最多的节点数为m，则B树为m阶树
B树的搜索方式
- 从根节点开始沿着起始位置查询
- 找到第一个搜索范围后，进入指针指向的孩子结点
- 沿着孩子结点依次比较，确定下一个范围后，即进入新的指针
- 重复以上步骤，找到结果后，返回，如果找到叶子结点，则返回NIL，因为页结点的指针指向了指针为NIL的哨兵结点
B树的特点
- m阶的B树每个节点，至多可以拥有m棵子树；
- 关键字集合分布再整棵树中
- 任何一个关键字出现且只出现再一个节点中
- 搜索在非叶子节点结束后，直接返回
- 搜索性能等价于在有序关键字集合内做一次二分查找
- B树的插入删除新的数据记录的操作，会破坏BTree的性质
  - 插入删除，需要对B树进行一次分裂合并转移等操作以保持B树性质
- B树的基本动态集合操作，见算法导论第18章；

基础概念回顾，详细学习包括算法导论B树的基本动态集合操作学习；以及MySQL B+ B-树底层的实现源码
MARK - PAGE278

B+Tree实现及索引原理

B+ 树

相较于B树，B+树
- n棵树的节点含有n个关键字，所有的关键字全都存储在页节点上，且叶子节点本身根据关键字大小顺序连接（链表）
- B+树的非叶子节点为索引部分，且节点中只包含其子树的根中的最大或最小关键字；
查询方式
- 查询方式和B树基本一致
- 不同点
  1. 查询时如果非叶子节点上的值与查询关键词一致，并不终止，而继续沿指针向下，知道叶子节点的位置；
- B+树的查询，无论成功与否，每次查询都会走一条从根节点到叶子节点的路径；
B+树的特性
- 所有关键字都在叶子节点上，叶子节点组成的链表有序
- 不可能非叶子节点命中后返回
- 非叶子节点相当于叶子节点的索引，叶子节点相当于存储数据的数据层
- B+树更适合与文件搜索系统，或者说与磁盘I/O交互的索引系统

B+Tree + 顺序访问指针

关系型数据库系统中，对经典的B+Tree进行了优化，增加了顺序访问指针
在相邻的叶子节点之间增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree
顺序访问指针很大程度上提高了区间搜索的性能
- 需要查询A到F之间的内容，当通过根节到到叶子的路径搜索到A后，使用顺序访问指针，很快就能找到F，并返回该区间的数据内容；
- 通过一个H高度的查询，一次可以访问到区间呢所有的数据

B+树的应用 - MySQL

实现索引的方式包括
- 红黑树
- B树
- B+树/B-树
索引本身的存储
- 索引本身可能会很大，不可能完全存储在内存中，索引通常以索引文件的形式存储在磁盘上；
- 索引的根节点在主存中，其他子树在磁盘存储，索引的数据结构需要尽可能的减少磁盘I/O操作的存取次数；

计算机存储原理

详细回顾CSAPP

主存
- 计算机将主存虚拟化为了一个一维线性的固定长度数组
- 物理层面主存为DRAM，动态随机读写存储器；
- 工作原理：
  - 读取
    - 系统需要读取主存时，将物理地址放在地址总线上传给主存，主存（控制器）读取信号后，解析信号，并定位到指定存储单元；
    - 主存将存储单元的数据放到数据总线上，其他共部件读取；
  - 写入
    - 系统将要写入的物理地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，并作出相应的操作；
- 主存的存取时间和存取次数成线性关系；
磁盘存取原理
- 磁盘由数个磁盘和磁头组成；每个磁头负责读取磁盘上的内容；
- 盘片上由多个同心磁道，所有盘片上半径相同的磁道组成了一个柱面；磁道沿着半径被划分为扇区，每个扇区为磁盘的最小存储单元；
- 读取数据
  - 系统将逻辑地址转给磁盘控制器，磁盘控制电路按照寻址逻辑将逻辑地址翻译为物理地址；
  - 磁头经过机械运动（寻道，耗费的时间为寻道时间，8ms~10ms），将磁头放在物理地址指定的扇区上，磁盘需要旋转到目标扇区（旋转时间）
- 局部性原理
  - 磁盘为了提高效率，会对数据进行预读，如只需要一个字节的数据，磁盘会将从该位置开始的一定长度的数据都放入内存；
  - 计算机科学-局部性原理：当一个数据被用到时，其附近的数据也通常会被使用；
- 页 page
  - 计算机管理存储器的逻辑块
  - 操作系统将磁盘存储的扇区分割为大小相等的块；
  - 每一块就是一页（通常为4kb）；
  - 主存和磁盘以页为单位进行数据交换；
  - 当程序需要读取的数据不在主存，出发缺页异常，操作系统向磁盘控制器发送读盘信号，磁盘会找到数据的起始地址开始，连续读入内存几页，然后异常返回，程序继续运行；

B-/+ Tree索引性能分析

B树就是B-树
- 对于B-树，检索一次需要从根节点开始到叶子节点，假设树的高度为h，则每次检索需要访问h个节点；利用操作系统的磁盘预读原理，将一个节点的大小设置为一个页 4kb; 每个节点只需要一次I/O操作就可以完全载入；
  - 新建节点，申请一个页的空间，保证节点在物理存储上也被存储在一个“页”中，计算机存储分配都会按页对其；
- 由于根节点常驻在内存中，B- Tree中的一次检索最多需要h-1次I/O操作；
  - 渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)
    h表示树的高度，d表示树的度，一颗树的度为树种每个节点度的最大值；
    实际应用中一棵树的度一般都非常大，大于100；树的高小于3；
    由于B-Tree的结构特点，所以他的搜索效率非常高，对磁盘的I/O操作不超过3次
红黑树 Red-Black-Tree
- 由于红黑树为特殊的二叉搜索树的，深度h较深；
- 由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
B+Tree
- B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：
```
dmax=floor(pagesize/(keysize+datasize+pointsize));
// floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
```
- 出度越大，一次I/O操作能够读取到主存的数据量越大，检索效率越高，而出度d的最大值，却决于当前一个页（存储一个节点），能够存储多少个指针结构（key+point)；
MySQL索引的实现
- MySQL包含两个主流的存储引擎，不同的引擎中索引的实现方式不同；
- MyISAM，InnoDB
  1. MyISAM索引的实现
    - MyISAM Engine使用B+Tree作为索引结构，树的叶子节点的Data域存放的是数据记录的地址；
    - 包含两种索引类型：
      - 主索引 Primary Key
        作为数据记录的主键，要求key必须唯一
        可以不存在主键
      - 辅助索引 Secondary key
        作为数据库中手动创建的查询索引，key可以重复
      - 在结构上两者都使用B+树，且根节点常驻内存；
    - 检索方式
      1. 同样使用B+树的检索方式，对索引进行检索
      2. 到达叶节点后，如果指定key或者数据范围存在，则从叶子节点的值域部分取出数据的地址；
      3. 读取相应地址的数据到主存并返回；
    - “非聚集”，因为数据和索引是分开的，用指针关联；
  2. InnoDB Engine
    - 同样使用B+Tree的索引结构
    - 与MyISAM的不同
      1. 表数据本身 - 按照B+Tree的结构组织为索引，叶子节点的值域部分保存了该数据记录的完整数据，且索引的Key为数据记录的主键，InnoDB表数据本身就是主键索引
        这样的索引方式为聚集索引
        因为表数据按照主键生成索引结构（按照主键聚集），所以InnoDB Engine要求必须有主键，且唯一
        如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
      2. InnoDB 辅助索引的叶子节点的值域部分存储相应数据记录的主键的值，而不是地址；
        这就表示InnoDB的辅助索引，引用了主键作为叶子节点的data；
        key在索引中以ASCII的形式存储
        所以，对于InnoDB Engine来说，对于手动创建的辅助索引来说，检索数据的过程，要找到对两个B+Tree进行检索，就是先检索辅助索引，到达对应的叶子节点的值域后获取记录主键，再根据主键在主索引中进行检索；
        这样的效率比直接使用主键检索要低一半；
    了解数据库Engine的原理，对使用有很大帮助，例如：
    1. 为什么不建议使用过长的字段作为主键
      因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
    2. 用非单调的字段作为主键在InnoDB中不是个好主意 (单调: 微积分概念，表示一个函数的单调递增或者单调递减)
      因为InnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
    学习地址

红黑树&B树应用及索引原理

算法导论（第三版）学习笔记 红黑树 + B树部分

第13章 红 黑 树

13.1 红黑树的性质

第18章 B 树

B+Tree实现及索引原理

B+ 树

B+Tree + 顺序访问指针

B+树的应用 - MySQL

计算机存储原理

B-/+ Tree索引性能分析

算法导论（第三版）学习笔记红黑树 + B树部分

第13章红黑树