00 – 背景知识

- B-Tree & B+Tree

??http://en.wikipedia.org/wiki/B%2B_tree
??http://en.wikipedia.org/wiki/B-tree

- 折半查找(Binary Search)

??http://en.wikipedia.org/wiki/Binary_search_algorithm

- 数据库的性能问题

? A. 磁盘IO性能非常低，严重的影响数据库系统的性能。
? B. 磁盘顺序读写比随机读写的性能高很多。

- 数据的基本存储结构

? A. 磁盘空间被划分为许多大小相同的块（Block）或者页(Page).
? B. 一个表的这些数据块以链表的方式串联在一起。
? C. 数据是以行（Row）为单位一行一行的存放在磁盘上的块中,如图所示.
? D. 在访问数据时，一次从磁盘中读出或者写入至少一个完整的Block。

01 – 数据基本操作的实现

??基本操作包括：INSERT、UPDATE、DELETE、SELECT。

- SELECT

??A. 定位数据
??B. 读出数据所在的块，对数据加工
??C. 返回数据给用户

- UPDATE、DELETE

??A. 定位数据
??B. 读出数据所在的块，修改数据
??C. 写回磁盘

- INSERT

??A. 定位数据要插入的页（如果数据需要排序）
??B. 读出要插入的数据页，插入数据.
??C. 写回磁盘

如何定位数据？
- 表扫描(Table Scan)

??A. 从磁盘中依次读出所有的数据块，一行一行的进行数据匹配。
??B. 时间复杂度 是O(n)， 如果所有的数据占用了100个块。尽管只查询一行数据，
???? 也需要读出所有100个块的数据。
??C. 需要大量的磁盘IO操作，极大的影响了数据定位的性能。

因为数据定位操作是所有数据操作必须的操作，数据定位操作的效率会直接影响所有的数据操作的效率。
因此我们开始思考，如何来减少磁盘的IO？
- 减少磁盘IO

? A. 减少数据占用的磁盘空间
?????压缩算法、优化数据存储结构
??B. 减少访问数据的总量
?????读出或写入的数据中，有一部分是数据操作所必须的，这部分称作 有效数据。剩余的
???? 部分则不是数据操作必须的数据，称为无效数据。例如，查询姓名是‘张三’的记录。
???? 那么这条记录是有效记录，其他记录则是无效记录。我们要努力减少无效数据的访问。

02 – 索引的产生

- 键(Key)

??首先，我们发现在多数情况下，定位操作并不需要匹配整行数据。而是很规律的只匹配某一个
??或几个列的值。 例如，图中第1列就可以用来确定一条记录。这些用来确定一条数据的列，统?
??称为键(Key) .

- Dense Index

? 根据减少无效数据访问的原则，我们将键的值拿过来存放到独立的块中。并且为每一个键值添
??加一个指针， 指向原来的数据块。如图所示,

? 这就是‘索引’的祖先Dense Index . 当进行定位操作时，不再进行表扫描。而是进行
? 索引扫描(Index Scan) ，依次读出所有的索引块，进行键值的匹配。当找到匹配的键值后，
??根据该行的指针直接读取对应的数据块，进行操作。假设一个块中能存储100行数据，
??10,000,000行的数据需要100,000个块的存储空间。假设键值列（+指针）占用一行数据
??1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储