数据库的原理-侧重索引

统计信息和过滤因子
分布统计信息 (信息分布不均衡.存在重复数据.正态数据.)和调优执行计划..
聚集簇索引.非聚集簇索引(索引文件的物理分布)
可索引谓词和不可索引谓词（Indexable Predicate and Non-Indexable Predicate）
匹配索引扫描和非匹配索引扫描（Matching Index Scan and Non-Matching Index Scan）
只索引扫描,取一次访问（One-Fetch Access）
唯一索引扫描和非唯一索引扫描（Unique Index Scan and Non-Unique Index Scan ）
随机io 1/80秒
顺序预取I/O时间开销的经验值同样是0.00125 秒/每次。即随机I/O效率的10倍。
通常意义上，一个表上的索引数量不宜超过5个
raid I/O并行和磁盘条带化（I/O Parallelism and Disk Striping） 
I/O预取（Prefetch I/O）
一次I/O的时间开销 = 磁盘臂寻道时间（seek time） + 磁盘旋转延迟（rotational latency） + 数据传输时间（transfer time）。其中寻道时间和旋转延迟是影响I/O时间的主要因素。

通常一次I/O顺序预取的数据页数为32页

缓冲池存在的唯一目的就是提高数据库系统性能。
缓冲池本质上是分配给数据库管理器管理的一块内存空间，用于读写数据页。（包括表行和索引数据页。内存中表行数据页称为缓存表）
索引按照结构可以分为有序索引（ordered index）和散列索引（hash index）两种基本类型。其中有序索引是基于值的顺序排序，根据值的排序进行索引值的查找。
而散列索引则是基于将值平均分布到若干散列桶（hash bucket）。根据散列函数确定索引值所在的散列桶。

稠密索引（dense index）和稀疏索引（sparse index）
我们将表中所有列值建立一个索引记录的索引称为稠密索引（dense index），将只为某些列值建立索引记录的索引称为稀疏索引（sparse index）
括Oracle数据库在内的大多数数据库产品采用的策略是使用散列桶（hash bucket）。即对于一个搜索码对应多个数据行的情况
其叶结点指针指向一个散列桶，再通过遍历散列桶来获取所有满足条件的行地址。（这个策略类似B树索引结构）


数据库的智能大脑
SQL语言也是一种编译型语言，需要SQL编译器编译后才能执行，但它与C、C++、Java等语言不同，SQL语言是一种非过程化语言，这意味着使用SQL进行操作的时候，你只需要指定你要达到什么目的，而无需指明要怎样达到目的。比如要查询EMPLOYEE的所有行，使用语句“Select * From EMPLOYEE”就行了，不需要规定该怎样查询这些行。
既然用户只需要解决“做什么”的问题，那么，“怎么做”的问题由谁来解决呢？
优化器（Optimizer）
解决“怎么做”问题的工具就是“优化器”。优化器也称查询优化器（Query Optimizer）
优化器在整个数据库系统中占据着至高无上的地位，它是数据库性能的决定因素，是所有数据库引擎中最重要的组件当前所有的数据库产品中，

这个进行优化选择的工作是由DB2优化器的另两大组件成本评估器（Estimator）和计划生成器（Plan Generator）完成的

sql 在数据库中的执行流程..
1.语法分析（Parse Query）
2.语义检查（Check Semantics）
3.查询重写（Rewrite Query）(优化sql语句)
4.优化访问计划（Optimizer Access Plan）
5.生成可执行代码（Generate Executable Code）(可以执行的机器码)
6.执行访问计划（Execute Plan）



块一般用到总空间的70% ,即不增加.为以后update insert 等富裕空间.



一次完整的输入输出（IO）操作的时间=磁盘轴旋转时间（旋转延迟）+磁盘臂移动时间（寻道时间）+数据传输时间。
三者所需时间的平均经验值为：0.004秒、0.008秒和0.0005秒。所以，一次完整的IO时间的经验值是0.0125秒，即1/80秒。
顺序io 大概是随机io 的10倍.



DB2是不允许行（记录）跨页的，即不允许行链接。但是允许行迁移（DB2中又称为行溢出），

公共和变量块头( Common and Variable Header)
头部包含了通用块信息，例如块的地址和段的类型 ( 例如表或者索引 )
表目录（Table Directory）
这部分信息包含了在这个块中该表或该索引的相关信息。
行目录（Row Directory）
这部分包含了数据块中的实际行的信息 ( 包括行数据区域中每行的地址 ) ，一旦数据块头部的这个行目录的空间被分配了，那么即使该行删除了，这段空间仍然不能回收。
因此一个当前为空的数据块，此区域包含数据块中存储的数据行的信息（每个数据行片断（ row piece ） 在行数据区（ row data area ）中的地址）。 [ 一个数据块中可能保存一个完整的数据行，也可能只保存数据行的一部分 ，所以文中使用 row piece] 。只有在数据块中插入（ insert ）新数据时，行目录区空间才会被重新利用。
头部信息区（Overhead ）
块头（ header/Common and Variable ），表目录（ Table Directory ），行目录（ Row Directory ）这三部分合称为头部信息区（ Overhead ）。头部信息区不存放数据，它存放的整个块的信息。头部信息区的大小是可变的。一般来说，头部信息区的大小介于 84 字节（ bytes ）到 107 字节（ bytes ）之间。
可用空间（Free Space）
可用空间是一个块中未使用的区域，这片区域用于新行的插入和已经存在的行的更新。可用空间也包含事务条目，当每一次 insert 、 update 、 delete 、 select ..for update 语句访问块中一行或多行数据，将会请求一条事务条目，事务条目的请求空间与操作系统相关，在多数操作系统中大约所需 23 个字节。
行数据（Row Data）
这部数据块包含了表或索引的数据，行也可能跨数据块，这也就是行迁移现象。

行链接和行迁移（Row Chaining and Migrating ）
行链接（ Row Chaining ）：如果我们往数据库中插入（ INSERT ）一行数据，这行数据很大，以至于一个数据块存不下一整行， Oracle 就会把一行数据分作几段存在几个数据块中，这个过程叫行链接（ Row Chaining ）。
如果一行数据是普通行，这行数据能够存放在一个数据块中；如果一行数据是链接行，这行数据存放在多个数据块中。
行链接又称为行跨页，Oracle允许行跨页，但DB2是不允许的。


B树

即二叉搜索树：
1. 所有非叶子结点至多拥有两个儿子（Left和Right）；
2. 所有结点存储一个关键字；
3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

B-树

是一种多路搜索树（并不是二叉的）：
1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字（至少2个关键字）；
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；

B+树

B+树是B-树的变体，也是一种多路搜索树：
1. 其定义基本与B-树同，除了：
2. 非叶子结点的子树指针与关键字个数相同；
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5. 为所有叶子结点增加一个链指针；
6. 所有关键字都在叶子结点出现；


B*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针：


B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；