00 – 背景知识
– B-Tree & B+Tree
http://en.wikipedia.org/wiki/B%2B_treehttp://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。
Fig. 1
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个块的数据。
https://blog.haohtml.com/archives/12132/
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。 Fig. 1 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个块的数据。