Skip to content

Commit d79d040

Browse files
JstarfishJstarfish
committed
binary search
1 parent dd6016c commit d79d040

93 files changed

Lines changed: 8303 additions & 8183 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/.obsidian/core-plugins-migration.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,5 +25,6 @@
2525
"file-recovery": true,
2626
"publish": false,
2727
"sync": false,
28-
"canvas": true
28+
"canvas": true,
29+
"bookmarks": true
2930
}

‎docs/.obsidian/core-plugins.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313
"note-composer",
1414
"command-palette",
1515
"editor-status",
16-
"starred",
16+
"bookmarks",
1717
"outline",
1818
"word-count",
1919
"file-recovery"

‎docs/.obsidian/workspace.json‎

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,9 +30,19 @@
3030
"source": false
3131
}
3232
}
33+
},
34+
{
35+
"id": "5fb9b5242c50d2a2",
36+
"type": "leaf",
37+
"state": {
38+
"type": "release-notes",
39+
"state": {
40+
"currentVersion": "1.3.5"
41+
}
42+
}
3343
}
3444
],
35-
"currentTab": 1
45+
"currentTab": 2
3646
}
3747
],
3848
"direction": "vertical"
@@ -77,6 +87,14 @@
7787
"type": "starred",
7888
"state": {}
7989
}
90+
},
91+
{
92+
"id": "123cfa366479ce4d",
93+
"type": "leaf",
94+
"state": {
95+
"type": "bookmarks",
96+
"state": {}
97+
}
8098
}
8199
]
82100
}
@@ -159,7 +177,7 @@
159177
"command-palette:Open command palette": false
160178
}
161179
},
162-
"active": "264bec0c6c3126ab",
180+
"active": "5fb9b5242c50d2a2",
163181
"lastOpenFiles": [
164182
"data-structure-algorithms/algorithm/Backtracking.md",
165183
"data-structure-algorithms/algorithm/未命名.md",

‎docs/.vuepress/config.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -167,7 +167,7 @@ function genDSASidebar() {
167167
children: [
168168
"complexity",
169169
"Sort",
170-
['Binary-Search', '二分查找'],
170+
['algorithm/Binary-Search', '二分查找'],
171171
['Recursion', '递归'],
172172
['Double-Pointer', '双指针'],
173173
['Dynamic-Programming', '动态规划'],

‎docs/data-management/.DS_Store‎

2 KB
Binary file not shown.

‎docs/data-management/MySQL/MySQL-Lock.md‎

Lines changed: 216 additions & 49 deletions
Large diffs are not rendered by default.

‎docs/data-management/MySQL/MySQL-Log.md‎

Lines changed: 20 additions & 21 deletions
Large diffs are not rendered by default.

‎docs/data-management/MySQL/MySQL-Storage-Engines.md‎

Lines changed: 28 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -182,6 +182,34 @@ SET default_storage_engine=NDBCLUSTER;
182182

183183

184184

185+
#### 数据页结构
186+
187+
页是 InnoDB 存储引擎管理数据的最小磁盘单位，一个页的大小一般是`16KB`。
188+
189+
`InnoDB`为了不同的目的而设计了许多种不同类型的`页`，比如存放表空间头部信息的页，存放`Insert Buffer`信息的页，存放`INODE`信息的页，存放`undo`日志信息的页等等等等。
190+
191+
B-Tree 节点就是实际存放表中数据的页面，我们在这里将要介绍页是如何组织和存储记录的；首先，一个 InnoDB 页有以下七个部分：
192+
193+
![](https://img.starfish.ink/mysql/innodb-b-tree-node.jpg)
194+
195+
有的部分占用的字节数是确定的，有的部分占用的字节数是不确定的。
196+
197+
| 名称 | 中文名 | 占用空间大小 | 简单描述 |
198+
| -------------------- | ------------------ | ------------ | ------------------------ |
199+
| `File Header` | 文件头部 | `38`字节 | 页的一些通用信息 |
200+
| `Page Header` | 页面头部 | `56`字节 | 数据页专有的一些信息 |
201+
| `Infimum + Supremum` | 最小记录和最大记录 | `26`字节 | 两个虚拟的行记录 |
202+
| `User Records` | 用户记录 | 不确定 | 实际存储的行记录内容 |
203+
| `Free Space` | 空闲空间 | 不确定 | 页中尚未使用的空间 |
204+
| `Page Directory` | 页面目录 | 不确定 | 页中的某些记录的相对位置 |
205+
| `File Trailer` | 文件尾部 | `8`字节 | 校验页是否完整 |
206+
207+
208+
209+
在页的 7 个组成部分中，我们自己存储的记录会按照我们指定的`行格式`存储到 `User Records` 部分。但是在一开始生成页的时候，其实并没有 `User Records` 这个部分，每当我们插入一条记录，都会从 `Free Space` 部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到 `User Records` 部分，当 `Free Space` 部分的空间全部被 `User Records` 部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，这个过程的图示如下：
210+
211+
![img](https://relph1119.github.io/mysql-learning-notes/images/05-02.png)
212+
185213
#### 如何存储表
186214

187215
MySQL 使用 InnoDB 存储表时，会将表的定义和数据索引等信息分开存储，其中前者存储在 `.frm` 文件中，后者存储在 `.ibd` 文件中。
@@ -243,28 +271,6 @@ ALTER TABLE 表名 ROW_FORMAT=行格式名称
243271

244272

245273

246-
#### 数据页结构
247-
248-
页是 InnoDB 存储引擎管理数据的最小磁盘单位，一个页的大小一般是`16KB`。
249-
250-
`InnoDB`为了不同的目的而设计了许多种不同类型的`页`，比如存放表空间头部信息的页，存放`Insert Buffer`信息的页，存放`INODE`信息的页，存放`undo`日志信息的页等等等等。
251-
252-
B-Tree 节点就是实际存放表中数据的页面，我们在这里将要介绍页是如何组织和存储记录的；首先，一个 InnoDB 页有以下七个部分：
253-
254-
![](https://img.starfish.ink/mysql/innodb-b-tree-node.jpg)
255-
256-
有的部分占用的字节数是确定的，有的部分占用的字节数是不确定的。
257-
258-
| 名称 | 中文名 | 占用空间大小 | 简单描述 |
259-
| -------------------- | ------------------ | ------------ | ------------------------ |
260-
| `File Header` | 文件头部 | `38`字节 | 页的一些通用信息 |
261-
| `Page Header` | 页面头部 | `56`字节 | 数据页专有的一些信息 |
262-
| `Infimum + Supremum` | 最小记录和最大记录 | `26`字节 | 两个虚拟的行记录 |
263-
| `User Records` | 用户记录 | 不确定 | 实际存储的行记录内容 |
264-
| `Free Space` | 空闲空间 | 不确定 | 页中尚未使用的空间 |
265-
| `Page Directory` | 页面目录 | 不确定 | 页中的某些记录的相对位置 |
266-
| `File Trailer` | 文件尾部 | `8`字节 | 校验页是否完整 |
267-
268274

269275

270276
> [踏雪无痕-InnoDB存储引擎](https://www.cnblogs.com/chenpingzhao/p/9177324.html)

‎docs/data-management/MySQL/MySQL-Transaction.md‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -264,13 +264,23 @@ InnoDB 的 MVCC，是通过在每行记录后面保存两个隐藏的列来实
264264

265265
MVCC 只在 COMMITTED READ（读提交）和 REPEATABLE READ（可重复读）两种隔离级别下工作。
266266

267-
267+
> 所谓的`MVCC`，就是通过生成一个`ReadView`，然后通过`ReadView`找到符合条件的记录版本（历史版本是由`undo日志`构建的），其实就像是在生成`ReadView`的那个时刻做了一次时间静止（就像用相机拍了一个快照），查询语句只能读到在生成`ReadView`之前已提交事务所做的更改，在生成`ReadView`之前未提交的事务或者之后才开启的事务所做的更改是看不到的。而写操作肯定针对的是最新版本的记录，读记录的历史版本和改动记录的最新版本本身并不冲突，也就是采用`MVCC`时，`读-写`操作并不冲突。
268268
269269
## 四、事务的实现
270270

271271
> 事务的隔离性是通过锁实现，而事务的原子性、一致性和持久性则是通过事务日志实现 。
272272
273+
### 一致性读（Consistent Reads）
274+
275+
事务利用`MVCC`进行的读取操作称之为`一致性读`，或者`一致性无锁读`，有的地方也称之为`快照读`。所有普通的`SELECT`语句（`plain SELECT`）在`READ COMMITTED`、`REPEATABLE READ`隔离级别下都算是`一致性读`，比方说：
276+
277+
```sql
278+
sql
279+
复制代码SELECT * FROM t;
280+
SELECT * FROM t1 INNER JOIN t2 ON t1.col1 = t2.col2
281+
```
273282

283+
`一致性读`并不会对表中的任何记录做`加锁`操作，其他事务可以自由的对表中的记录做改动。
274284

275285
### 事务日志
276286

0 commit comments

Comments
 (0)