文件与磁盘

数据结构

B+树

m阶B+树

1.每个结点至多有m个子女

2.除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；

3.有k个子女的结点必有k个关键字。

B+树的卫星数据只存于叶子结点，相对B-树查询性能稳定，且范围查询容易



LSM树

Log-Structured Merge-Tree

待补充。。

文件控制块

文件系统将磁盘空间以块为单位进行划分，每个文件占据若干块，然后再通过一个文件控制快FCB记录每个文件占据的磁盘数据块。



Linux inode文件控制块

• inode记录着文件权限、所有者、修改时间、文件大小等文件属性信息，以及文件数据块硬盘地址索引。

• 最多15个索引，12个直接索引+1-3级间接索引



Raid



Raid0、1、10、5、6

待补充



数据结构及算法

时间、空间复杂度

时间复杂度：算法执行语句的次数

多项式时间复杂度：O(1)、O(n^a)、O(log(n))

空间复杂度：一个算法在运行过程中临时占用存储空间的量度



NP问题

P:能在多项式时间复杂度内解决的问题

NP：能在多项式时间复杂度内验证答案正确与否的问题

NP？=P

NP-hard：比NP问题更难的问题

NP完全问题：是一个NP-hard问题，也是一个NP问题



数据结构

数组、链表、hash表、栈、

树

红黑树VS平衡二叉树

红黑树3次旋转就能恢复红黑树，时间复杂度O(1),大量删除时红黑树效率更高，查询效率较平衡二叉树差

跳表

算法

• 穷举算法

• 贪心算法

• 动态规划

• 递归算法

•