数据库通用结构

数据库系统管理数据,这里的数据按照表的概念在真正存储时按照行或者列进行聚合 查询的操作就是在这些被聚合的块上所进行的.

一般的操作是插入写入到数据文件中 同时更新索引文件. 查询时根据(有序的)索引文件进行查询 从索引文件中获取到足够的关于整个数据块在数据文件中位置 在去查询数据块

查询依赖于顺序,最好的管理的数据结构就是树,但2叉树之类的树在更新时会导致大量的变更.同时因为内存不是持久化的,所以如果直接用2叉树在磁盘上存储 就会导致大量的磁盘IO,无法保证性能.

B(B+)树,就是对磁盘的这种性质做了优化的树的结构 主要体现在树的每个节点能够存储N个值 降低了高度(增加了扇出)

B树 物理(磁盘)表现形式

分槽页与单元格

B树的一个节点(页) 结构可以如图3.5 表示 这里的指针其实就是对应单元格在文件中的偏移值. 注意的是单元格时无序的(减少插入成本),但单元格的指针是有序,这样就把排序的成本放在了这些指针的更新上 分槽页的有趣结构在于指针和单元格在两头.类似于固定大小的控制结构体,和不停辗转腾挪(gc)的raw data 单元格中的页id可以理解为B树结构中指向子树的指针.

键值太长了怎么办? 例如超长的字符串

页的大小是固定的 (4k),我们会使用类似链表的感觉将两个页链接起来 主页中维护溢出页的指针(位置).