<commit_before>---
layout: post
title: 数据库开发基础理论知识点罗列
category: 理论学习
keywords: 数据库, KSTORE, 底层, C
---

# 数据库开发基础理论知识点罗列

## 1. 理论


### 1.1 数据库相关基础知识

#### 1.1.1 ACID以及靠什么保证ACID
+ A 原子性			事务中的操作要么全部成功，要么全部失败。
+ C 一致性			从一个合法状态到另外一个合法状态，通过例如约束、触发器等。
+ I 隔离性/独立性	并发处理多个事务时，和串行化执行的效果对系统的影响时一样的。
+ D 持久性			一个事务被提交之后，状态保持不变，不会因为断电、崩溃等导致变化。

#### 1.1.2 DDL/DML/DCL/DQL
+ CREATE/DROP/ALTER
+ INSERT/UPDATE/DELETE/SELECT
+ GRANT 

### 1.2 编程基础知识

#### 1.2.1 多线程
#### 1.2.2 c基础
##### 1.2.2.1 static作用
+ 静态局部变量，定义在函数体内，作用域为函数体内，生命周期为整个程序运行期内，多次调用函数改变static修饰的静态局部变量，会一直记录。
+ 静态全局变量，定义在函数体外，作用域为当前文件，生命周期为整个程序运行期内，多次调用函数改变static修饰的静态全局变量，会一直记录。
+ 静态函数，作用域在当前文件内，不允许其他文件调用。

##### 1.2.2.2 ifndef/define/endif作用
+ 一般用在.h文件中，防止重复引用头文件
+ 也可用在代码中，控制某些部分的编译可见性

##### 1.2.2.3 include <file.h+和include "file.h"区别
+ 查找路径不同，前者去标准库找，后者在当前工作路径找。

##### 1.2.2.4 全局变量和局部变量存储位置
+ 全局变量在静态数据区，局部变量在堆栈中。

##### 1.2.2.5 什么是平衡二叉树
+ 左右子树都是平衡二叉树，且左右子树的深度差的绝对值不大于1。

##### 1.2.2.6 堆栈溢出引发原因
+ 层次过多的递归调用
+ 没有回收垃圾

##### 1.2.2.7 排序时间复杂度
+ 冒泡排序，O(n^2)

##### 1.2.2.8 全局变量引用方式
+ 引用头文件
+ extern方式

##### 1.2.2.9 const作用
+ 只读，常量，保证修饰的值不会改变
+ int const a;==const int a;
+ 表示整数a的值不可变
+ const int*a;*a不可变，a可变
+ int *const a;a可变，*a不可变
+ int const* a const;而这均不可变

##### 1.2.2.10 volatile作用及含义
+ 告诉编译器该值易变，不要从寄存器中读取该值的备份。

##### 1.2.2.11 结构联合的区别
+ 结构体成员各有各的存储位置
+ 联合成员共用一块地址

##### 1.2.2.12 内存分区方式及区别
+ 静态存储区，编译时分配，生命周期到程序运行结束
+ 栈，运行时局部变量申请，生命周期到离开函数
+ 对，动态分配，程序员手动申请释放。

##### 1.2.2.13 const #define优点
+ const有数据类型，会通过编译器进行安全检查，而define不会。

##### 1.2.2.14 数组和指针区别
+ 数组在静态存储区或栈上创建，不允许改变指向。
+ 指针可以指向任意类型的值。
+ sizeof可以算出数组大小，sizeof只能算出指针大小(一般为4字节)

##### 1.2.2.15 bool/int/float/指针与0值比较
+ bool if (!a)
+ int if (a == 0)
+ float const EXPRESSION EXP=0.000001; if (a < EXP && a + -EXP)
+ pointer if (a == NULL) 

##### 1.2.2.16 带参宏和函数优缺点
|带参宏|函数|
|处理时间|编译时期|程序运行时|
|参数类型|无类型|定义实参、形参类型|
|处理过程|不分配内存|分配内存|
|运行速度|不占运行时间|调用和返回占用时间|

##### 1.2.2.17 用两个栈实现队列的功能
> 假设A、B两栈
> 入队:
> 将新元素push到栈A中。
 
> 出队:
> 判断栈B是否为空
> 如果为空，将栈A中所有元素依次pop出，并push到栈B
> 将栈B的栈顶元素pop出。

##### 1.2.2.18 位运算
+ set |=
+ unset &=~

##### 1.2.2.19 指针、函数指针、指针函数
	int* a;
	int a[10];
	int *a[10];
	int (*a)(int);
	int (*a[10])(int);

##### 1.2.2.20 宏实现加法
`#define SUM(x) ((x)+(x))`

##### 1.2.2.21 单向链表删除节点
	a = p->next;
	p->next=p->next->next;

##### 1.2.2.22 各种占位符
	%d
	%o
	%x

##### 1.2.2.23 进程间通信
+ 消息队列
+ 共享内存
+ socket
+ 管道



## 2. 编程

### 2.1 各种排序及其时间复杂度
| 排序方法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 
| - | - | - | - | - | - | 
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | 
| 希尔排序 | O(nlogn)-O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 | 
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn)-O(n) | 不稳定 |

### 2.2 文件读写

### 2.3 各种遍历，树，图<commit_msg>修改表格格式，去掉首尾的竖线<commit_after>---
layout: post
title: 数据库开发基础理论知识点罗列
category: 理论学习
keywords: 数据库, KSTORE, 底层, C
---

# 数据库开发基础理论知识点罗列

## 1. 理论


### 1.1 数据库相关基础知识

#### 1.1.1 ACID以及靠什么保证ACID
+ A 原子性			事务中的操作要么全部成功，要么全部失败。
+ C 一致性			从一个合法状态到另外一个合法状态，通过例如约束、触发器等。
+ I 隔离性/独立性	并发处理多个事务时，和串行化执行的效果对系统的影响时一样的。
+ D 持久性			一个事务被提交之后，状态保持不变，不会因为断电、崩溃等导致变化。

#### 1.1.2 DDL/DML/DCL/DQL
+ CREATE/DROP/ALTER
+ INSERT/UPDATE/DELETE/SELECT
+ GRANT 

### 1.2 编程基础知识

#### 1.2.1 多线程
#### 1.2.2 c基础
##### 1.2.2.1 static作用
+ 静态局部变量，定义在函数体内，作用域为函数体内，生命周期为整个程序运行期内，多次调用函数改变static修饰的静态局部变量，会一直记录。
+ 静态全局变量，定义在函数体外，作用域为当前文件，生命周期为整个程序运行期内，多次调用函数改变static修饰的静态全局变量，会一直记录。
+ 静态函数，作用域在当前文件内，不允许其他文件调用。

##### 1.2.2.2 ifndef/define/endif作用
+ 一般用在.h文件中，防止重复引用头文件
+ 也可用在代码中，控制某些部分的编译可见性

##### 1.2.2.3 include <file.h+和include "file.h"区别
+ 查找路径不同，前者去标准库找，后者在当前工作路径找。

##### 1.2.2.4 全局变量和局部变量存储位置
+ 全局变量在静态数据区，局部变量在堆栈中。

##### 1.2.2.5 什么是平衡二叉树
+ 左右子树都是平衡二叉树，且左右子树的深度差的绝对值不大于1。

##### 1.2.2.6 堆栈溢出引发原因
+ 层次过多的递归调用
+ 没有回收垃圾

##### 1.2.2.7 排序时间复杂度
+ 冒泡排序，O(n^2)

##### 1.2.2.8 全局变量引用方式
+ 引用头文件
+ extern方式

##### 1.2.2.9 const作用
+ 只读，常量，保证修饰的值不会改变
+ int const a;==const int a;
+ 表示整数a的值不可变
+ const int*a;*a不可变，a可变
+ int *const a;a可变，*a不可变
+ int const* a const;而这均不可变

##### 1.2.2.10 volatile作用及含义
+ 告诉编译器该值易变，不要从寄存器中读取该值的备份。

##### 1.2.2.11 结构联合的区别
+ 结构体成员各有各的存储位置
+ 联合成员共用一块地址

##### 1.2.2.12 内存分区方式及区别
+ 静态存储区，编译时分配，生命周期到程序运行结束
+ 栈，运行时局部变量申请，生命周期到离开函数
+ 对，动态分配，程序员手动申请释放。

##### 1.2.2.13 const #define优点
+ const有数据类型，会通过编译器进行安全检查，而define不会。

##### 1.2.2.14 数组和指针区别
+ 数组在静态存储区或栈上创建，不允许改变指向。
+ 指针可以指向任意类型的值。
+ sizeof可以算出数组大小，sizeof只能算出指针大小(一般为4字节)

##### 1.2.2.15 bool/int/float/指针与0值比较
+ bool if (!a)
+ int if (a == 0)
+ float const EXPRESSION EXP=0.000001; if (a < EXP && a + -EXP)
+ pointer if (a == NULL) 

##### 1.2.2.16 带参宏和函数优缺点
|带参宏|函数|
|处理时间|编译时期|程序运行时|
|参数类型|无类型|定义实参、形参类型|
|处理过程|不分配内存|分配内存|
|运行速度|不占运行时间|调用和返回占用时间|

##### 1.2.2.17 用两个栈实现队列的功能
> 假设A、B两栈
> 入队:
> 将新元素push到栈A中。
 
> 出队:
> 判断栈B是否为空
> 如果为空，将栈A中所有元素依次pop出，并push到栈B
> 将栈B的栈顶元素pop出。

##### 1.2.2.18 位运算
+ set |=
+ unset &=~

##### 1.2.2.19 指针、函数指针、指针函数
	int* a;
	int a[10];
	int *a[10];
	int (*a)(int);
	int (*a[10])(int);

##### 1.2.2.20 宏实现加法
`#define SUM(x) ((x)+(x))`

##### 1.2.2.21 单向链表删除节点
	a = p->next;
	p->next=p->next->next;

##### 1.2.2.22 各种占位符
	%d
	%o
	%x

##### 1.2.2.23 进程间通信
+ 消息队列
+ 共享内存
+ socket
+ 管道



## 2. 编程

### 2.1 各种排序及其时间复杂度
排序方法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性
- | - | - | - | - | -
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定
直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定
希尔排序 | O(nlogn)-O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn)-O(n) | 不稳定

### 2.2 文件读写

### 2.3 各种遍历，树，图
{'fraction_non_alphanumeric': 0.22438255386232264, 'fraction_numerical': 0.057803468208092484, 'mean_word_length': 3.9097162510748067, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 46, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1088319', 'n_tokens_mistral': 4566, 'n_tokens_neox': 4987, 'n_words': 485}