数据库技术基础
1.数据库系统：数据库，硬件，软件，人员
2.DBMS（数据库管理系统）的功能：数据定义，数据库操作，数据库运行管理，数据组织、存储和管理，数据库的建立和维护，与其他软件系统的通信功能等
3.DBMS 的特征：数据结构化且统一管理，有较高的数据独立性，数据控制功能（数据库的安全性保护、数据的完整性、并发控制、故障恢复）
4.DBMS 分类：
关系数据库系统（实体间的联系用关系表示）
面向对象的数据库系统（以对象形式对数据建模）
对象关系数据库系统（在关系数据模型基础上提供处理新的数据类型操作的能力）
5.数据库系统体系结构：
集中式（数据、数据管理、数据库功能等都集中在一起）
分布式（物理上分布+逻辑上分布）
C/S 模式（客户端负责数据表示服务、服务器负责数据库服务）
并行结构（多个 CPU 物理上连在一起处理）
6.数据库的三级模式：
概念模式（数据库中全部数据的逻辑结构和特征的描述、只涉及型的描述而不涉及具体的值）
外模式（用户与数据库系统的接口、用户用到那部分数据的描述）
内模式（数据物理结构和存储方式的描述、数据在数据库内部的表示方式）
外模式对应视图；概念模式对应基本表；内模式对应存储文件
7.数据库的两级映像：
概念模式/内模式映射（实现概念模式与内模式的转换）
外模式/概念模式映射（实现外模式与概念模式的转换）
8.数据的独立性：
物理独立性（数据库的内模式改变时数据的逻辑结构不变）
逻辑独立性（用户的应用程序与数据库的逻辑结构相互独立）
9.数据模型：
概念数据模型（E-R 模型等）
基本数据模型（层次模型：用树型结构表示数据间的联系；网状模型：用网络结构表示数据间的联系；关系模型：用表格结构表示实体间的联系；面向对象模型：对象标识+封装+对象的属性+类和类层次+继承）
10.数据模型三要素：数据结构，数据操作，数据的约束条件
11.E-R 图：实体（矩形），联系（菱形），属性（椭圆形）
12.完整性约束：实体完整性，参照完整性，用户自定义完整性
13.关系代数运算：并，交，差，笛卡尔积，投影，选择，连接，除
并：两个关系不同的部分，S1∪S2→S1和S2不同的记录
交：两个关系相同的部分，S1∩S2→S1和S2相同的记录
差：前一个关系有而后一个关系没有的部分，S1-S2→S1有但S2没有记录
连接：属性相连，去掉重复列
笛卡尔积：两个关系每条记录都连接一次
投影：指定属性展示出来
选择：指定记录展示出来
14.SQL 语言的特点：综合统一，高度非过程化，面向集合的操作方式，两种使用方式（自含式、嵌入式），语言简洁易学易用
15.SQL 语言的组成：语数据定义言，交互式数据操纵语言，事务控制，嵌入式SQ 和动态SQL，完整性，权限管理
16.SQL 数据定义：创建（create），修改（alter），删除（drop）：表（table），视图（view[as select]），索引（index[on]）
17.SQL 数据查询：select...from...where...group by...having...order by...
18.插入数据：insert into...values...
19.修改数据：update...set...=...where...
20.删除数据：delete from...where...
21.授权：grant...on...to...(with grant option)
22.回收权限：revoke...on...from...
23.函数依赖：反映属性间的联系（X→Y）；
完全函数依赖：（学生 ID，所修课程 ID）→成绩；
部分函数依赖 ：（学生 ID，所修课程 ID）→学生姓名；
平凡函数依赖：X→Y 且 Y 包含于X；
非平凡函数依赖：X→Y 且Y 不包含于X；
传递函数依赖：X→Y，Y→Z
求候选键：
1、将函数依赖转化为有向图
2、找出入度为0的属性（或属性集合），以该属性（或属性集合）为起点，尝试遍历有向图，若能遍历完所有节点，则为一个候选键。
3、若没有入度为0的节点，找中间节点进行遍历
例子：关系R（A1，A2，A3，A4），函数依赖为F={A1→A2，A3→A2，A2→A3，A2→A4}
有向图为：
A1入度为0，且能够遍历完所有节点，所以A1为候选键
24.规范化：
1NF：每个分量都不可再分；
2NF：消除非主属性对码的部分函数依赖；
3NF：消除非主属性对码的传递函数依赖
25.模式分解标准：无损连接，保持函数依赖
26.事务的 ACID 性质：原子性，一致性，隔离性，持久性
27.事务管理：事务开始（begin transaction），事务提交（commit），事务回滚（rollback）
28.数据库故障：事务内部故障，系统故障，介质故障，计算机病毒
29.数据备份方法：静态转储和动态转储，海量转储和增量转储，日志文件
30.数据恢复步骤：反向扫描文件日志，对事物的更新操作执行逆操作，继续反向扫描和更新，直到事务的开始标志
31.并发控制的技术：封锁（写锁、读锁）
32.数据不一致性：丢失修改，不可重复读，读脏数据
33.在数据库逻辑结构设计阶段，需要（需求分析）阶段形成的（需求说明文档、数据字典和数据流图）作为设计依据
数据结构
1.数据结构：数据元素的集合及元素间的相互关系和构造方法
2.线性表的存储结构：顺序存储，链式存储
3.单链表节点：typedef struct node{ int data; struct node *link; }NODE,*LinkList;
4.双向链表：每个节点有两个指针，分别指出直接前驱和直接后继
5.循环链表：尾节点指针指向第一个节点
6.静态链表：借助数组来描述线性表的链式存储结构
7.栈：后进先出；初始化栈：InitStack(S) 判栈空：StackEmpty(S) 入栈：Push(S,x) 出栈：Pop(S) 读取栈顶元素：Top(S) 顺序存储+链式存储
8.队列：先进先出，尾入头出；初始化队：初始化队：InitQueue(Q) 判队空：Empty(Q) 入
队列的特点是先进先出，若用循环单链表表示队列，则：入队和出队操作都不需要遍历链表
解析：入队和出队都只需移到指针指向位置
入队：新节点s->next指向首结点，然后rear->next指向新的结点s
出队：rear->next=rear->next->next
9.串：仅由字符构成的有限序列，是取值范围受限的线性表
10.数组：定长线性表在维数上的扩张，一般不做插入删除运算
11.矩阵：
特殊矩阵（元素分布有一定的规律：对称矩阵、三角矩阵、对角矩阵）；
稀疏矩阵（非零元素远少于零元素且律：用三元组存储(行号，列号，值)）
12.广义表（表中有表）：表头（表中第一个元素）；表尾（表中除去表头剩下的部分）
13.树：递归的，元素之间有明显的层次关系
14.完全二叉树应采用顺序存储结构，一般二叉树则应采用链式存储结构
15.二叉树的链式存储结构：typedef struct BiTnode{ int data; struct BiTnode *lchild, *rchild; }BiTnode, *BiTree;
16.二叉树的遍历：先序遍历（先访问根节点），中序遍历（第二访问根节点），后序遍历（最后访问根节点），层序遍历（利用队列、每次出同一层的节点时进他们的子节点层）
17.线索二叉树：加上线索（直接前驱和直接后继）的二叉树
18.最优二叉树（哈夫曼树）：一类带权路径长度最短的树
19.树的存储结构：双亲表示法（顺序存储）；孩子表示法（链式存储）；孩子兄弟表示法（链式存储，两个指针分别为第一个孩子和下一个兄弟）
20.图：一个节点的前驱节点和后继节点数目没有任何限制
21.图的表示：G=(V，E)；V：顶点的集合；E：边的集合
22.网：边带权值的图
23.图的相关概念
24.图的存储结构：邻接矩阵表示法，邻接链表表示法
25.图的遍历：深度优先搜索，广度优先搜索
26.生成树：极小连通子图，针对连通图
27.最小生成树（权值和最小的生成树）
算法：
普尼姆算法（在相邻边的基础上求最小，与边数无关，适于边稠密的网）；
克鲁斯科尔算法（在不构成环的基础上找最小边直至连通，与顶点数无关，适于边稀疏的网）
28.AOV 网：有向图中顶点表示活动，有向边表示活动间的优先关系
29.拓扑排序：将AOV 网中所有顶点按优先顺序排成一个线性序列的过程
30.AOE 网：有向图中有向边表示活动，边上的权值表示该活动持续的时间
31.关键路径：从源点到汇点的路径中长度最长的
32.最短路径：从源点到其余各顶点的最短路径-----迪杰斯克拉算法
33.平均查找长度：关键字和给定值进行过比较的记录个数的平均值
34.静态查找方法：顺序查找；折半查找；分块查找
35.动态查找：表结构本身在查找过程中是动态生成的
36.二叉排序树：左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值
37.平衡二叉树（AVL 树）：左子树和右子树高度之差的绝对值不超过 1
38.B_树（m 阶）：每个节点子树个数<=m，根节点子树个数=0 或>=2，其他节点子树个数=0或>=m/2
39.哈希表：通过哈希函数（以记录的关键字为自变量）得到记录的存储地址；定长按一定函数规律存放数据；哈希地址+关键字
40.哈希表的重点：构造哈希函数（直接定址法，数字分析法，平方取中法，折叠法，随机数法，除留余数法）；解决冲突（开放定址法，链地址法，再哈希法）
41.简单排序（时间复杂度 O(n2)，空间复杂度 O(1)）
直接插入排序（插入第 i 个时前 i-1 个以排序好）
冒泡排序（相邻两个比较排序，每次循环确定一个极值）
简单选择排序（第 i 个依次与后面每个元素比较排序，每次循环确定一个极值，不稳定）
42.高端内部排序：
希尔排序（先将整个序列分割成若干序列分别进行直接插入排序，再对整个序列进行一次直接插入排序，不稳定）；
快速排序（将整个记录分割成独立的两部分，两个指针分别指向对应部分的两端，往中间移动比较排序，递归，不稳定）；
堆排序（建立初始堆输出并删除堆顶关键字，再建立新堆得到新的关键字依次输出，不稳定）
归并排序（将若干个有序序列合并为新的有序序列）；
基数排序（按组成关键字的各个数位的值进行排序）
43.排序算法的时间复杂度、空间复杂度以及是否是稳定排序
直接插入排序、希尔排序、直接选择排序、冒泡排序：O(n^2)，O(1)
稳定：直接插入、冒泡、归并、基数
对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用：堆排序
解析：对于希尔排序、直接插入排序，只有在排序过程后才能确保全部序列以及前k个元素的最终排序。
记忆：快速排序时间复杂度【最好和最坏】和空间复杂度，不稳定排序
直接插入排序：从数组的第二位开始，依次倒叙向前遍历排序，满足条件则交换顺序
时间复杂度是O(n2)，空间复杂度是O(1)，稳定排序
private void InsertSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
// 标志位，防止待插入元素最小
boolean flag = false;
int cur = array[i];
for (int j = i - 1; j > -1; j--) {
// 当前值和它前面的值比较，如果比前面的值小，前面的值后移，当前值替换前面的值；否则设置标识位
if (cur < array[j]) {
array[j + 1] = array[j];
array[j] = cur;
} else {
flag = true;
break;
}
}
if (!flag) {
array[0] = cur;
}
}
}希尔排序：对直接插入排序的优化，将待排序的数组元素按下标的一定增量分组，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
时间复杂度是O(nlog2n)，空间复杂度是O(1)，非稳定排序
private void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 3for + if
for (int d = arr.length/2; d >= 1; d = d/2) {
// 增量后半截
for (int i = d; i < arr.length; i++) {
// 增量前半截
for (int j = i - d; j > -1; j -= d) {
if (arr[j] > arr[j + d]) {
// 后半截和前半截差量进行插入排序
int tmp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = tmp;
}
}
}
}
}简单选择排序：每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，例：21 48 21* 63 17，第一趟排序，21与17交换，导致21与21*的相对位置发生变化
时间复杂度是O(n2)，空间复杂度是O(1)，不稳定排序
private void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
// 记录每次循环中的最小值
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 最小值不是当前值，交换位置
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}冒泡排序：对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
时间复杂度是O(n2)，空间复杂度是O(1)，稳定排序
private void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
boolean flag = false;
// 每次冒最大值到数组最后一位
for (int j = 0; j < arr.length - i -1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
// 本次循环没有移动位置，说明数组已有序，退出循环
if (!flag) {
break;
}
}
}堆排序：过程可以具体分为三步，创建堆，调整堆，堆排序。
- 创建堆，以数组的形式将堆中所有的数据重新排序，使其成为最大堆/最小堆。
- 调整堆，调整过程需要保证堆序性质：在一个二叉堆中任意父节点大于其子节点。
- 堆排序，取出位于堆顶的第一个数据（最大堆则为最大数，最小堆则为最小数），放入输出数组B中【也可以是它自己】，再将剩下的堆做调整，堆的迭代/重复运算直至输入数组A中只剩下最后一个元素。
时间复杂度是O(n*log(n))，空间复杂度是O(1)，不稳定排序
private void heapSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
// 调整堆
for (int j = cur; j > 0; j--) {
if (arr[i] > arr[i/2]) {
swap(arr, i, i/2);
}
}
// 排序堆
swap(arr, i, 0);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}快速排序：选择一个基准值，一轮排序后，基准值左边的值都比它小，右边的值都比它大；对基准值左右两边的数进行相同的操作，直到基准值左右两边的值只有一个
时间复杂度是O(nlog n)，空间复杂度是O(logn)，不稳定排序
划分过程中，最佳的基准元素选择的方法是选择待划分数组的（中位数）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（O(n)）
中位数
private void fastSort(int[] arr, int begin, int end) {
// 记录每一次开始和结束位置，如果 begin >= end 递归结束
int i = begin;
int j = end;
if (begin >= end) {
return;
}
// 选出哨兵元素【i和j】和基准元素
int base = arr[begin];
while (i < j) {
// 从右开始选择第一个比基准小的值
while (arr[j] >= base && i < j) {
j--;
}
// 从左开始选择第一个比基准大的值
while (arr[i] <= base && i < j) {
i++;
}
// 交换i和j的值
if (i != j) {
swap(arr, i, j);
}
}
// 当i==j时，当前值和基准值做交换，作为新一轮基准值
swap(arr, i, begin);
// 基准左边值
fastSort(arr, begin, i - 1);
// 基准右边值
fastSort(arr, i + 1, end);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}归并排序：分治法，将数组拆分成一个个小的数组，排序后，再合并成一个大的数组
时间复杂度是O(nlogn)【合并的平均时间复杂度为O(n)，完全二叉树的深度为log2n】，空间复杂度是O(n)，稳定排序
public void main(String[] args) {
int[] sourceArr = new int[]{9, 3, 1, 4, 2, 7, 8, 6, 5};
int[] mergeArr = new int[sourceArr.length];
mergeSort(sourceArr, mergeArr, 0, sourceArr.length - 1);
System.out.println(Arrays.toString(sourceArr));
}
private static void mergeSort(int[] sourceArr, int[] mergeArr, int low, int high) {
if (low >= high) {
return;
}
int mid = (low + high)/2;
// 拆分左边数组
mergeSort(sourceArr, mergeArr, low, mid);
// 拆分右边数组
mergeSort(sourceArr, mergeArr, mid + 1, high);
// 合并
merge(sourceArr, mergeArr, low, high, mid);
}
private static void merge(int[] sourceArr, int[] mergeArr, int low, int high, int mid) {
int i = low;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= high) {
if (sourceArr[i] <= sourceArr[j]) {
mergeArr[k++] = sourceArr[i++];
} else {
mergeArr[k++] = sourceArr[j++];
}
}
// 左边剩余元素填充进临时数组中
while (i <= mid) {
mergeArr[k++] = sourceArr[i++];
}
// 右边剩余元素填充进临时数组中
while (j <= high) {
mergeArr[k++] = sourceArr[j++];
}
// 临时数组值拷贝回原数组
k = 0;
while(low <= high){
sourceArr[low++] = mergeArr[k++];
}
}例：对基本有序的整数排序
