MYDB项目详解

MYDB

MYDB 分为后端和前端，前后端通过 socket 进行交互。前端（客户端）的职责很单一，读取用户输入，并发送到后端执行，输出返回结果，并等待下一次输入。MYDB 后端则需要解析 SQL，如果是合法的 SQL，就尝试执行并返回结果。不包括解析器，MYDB 的后端划分为五个模块，每个模块都又一定的职责，通过接口向其依赖的模块提供方法。五个模块如下：

Transaction Manager（TM）
Data Manager（DM）
Version Manager（VM）
Index Manager（IM）
Table Manager（TBM）

五个模块的依赖关系如下：

MYDB 模块依赖

从这个依赖图中，拓扑排序一下就能看出实现顺序。本教程的实现顺序是 TM -> DM -> VM -> IM -> TBM

每个模块的职责如下：

TM 通过维护 XID 文件来维护事务的状态，并提供接口供其他模块来查询某个事务的状态。
DM 直接管理数据库 DB 文件和日志文件。DM 的主要职责有：1) 分页管理 DB 文件，并进行缓存；2) 管理日志文件，保证在发生错误时可以根据日志进行恢复；3) 抽象 DB 文件为 DataItem 供上层模块使用，并提供缓存。
VM 基于两段锁协议实现了调度序列的可串行化，并实现了 MVCC 以消除读写阻塞。同时实现了两种隔离级别。
IM 实现了基于 B+ 树的索引，BTW，目前 where 只支持已索引字段。
TBM 实现了对字段和表的管理。同时，解析 SQL 语句，并根据语句操作表。

TM

让我们通过一个假想的例子来详解一个 XID 文件的结构和如何利用它来记录事务的状态。假设我们的系统已经处理了几个事务，并且事务的 XID 分别是从 1 到 5。我们将看到如何在 XID 文件中记录这些事务的状态。

XID 文件结构

文件的第一部分是一个8字节的数字，表示当前文件所记录的事务总数。
接下来的部分是每个事务的状态，每个状态占用1字节空间。

事务状态编码

假设我们用以下编码表示不同的事务状态：

0x00 - active (活动)
0x01 - committed (已提交)
0x02 - aborted (已撤销)

假设的 XID 文件内容

假设我们的系统中有5个事务的状态如下：

XID 1 - committed
XID 2 - aborted
XID 3 - committed
XID 4 - active
XID 5 - committed

文件布局

文件的具体布局将如下所示（数字表示事务的状态编码，每个数字代表1字节）：

头部（8字节）: 存储数字 5 (因为有5个事务)
事务1的状态（1字节）: 0x01 (committed)
事务2的状态（1字节）: 0x02 (aborted)
事务3的状态（1字节）: 0x01 (committed)
事务4的状态（1字节）: 0x00 (active)
事务5的状态（1字节）: 0x01 (committed)

文件示例的字节表达：

1
2
3

css
Copy code
[00 00 00 00 00 00 00 05][01][02][01][00][01]

这里：

[00 00 00 00 00 00 00 05] 是文件头部的8字节，表示管理的事务总数为5。
后续的每个 [XX] 表示一个事务的状态，从 XID 1 到 XID 5。

通过这样的布局，TransactionManager 可以轻松定位任何事务的状态信息。例如，如果想知道 XID 4 的状态，可以直接跳到文件的第12字节位置（头部8字节 + 前三个事务各占1字节 + 1字节偏移量因为事务ID从1开始）。这种方法提供了快速访问和更新事务状态的能力，非常适合需要高效事务处理的数据库系统。

TM问题

1.如何保证文件不发生问题
通过检查前8个字节查看事务的数量之后计算总的字节数与文件的总字节数比较，来保证问题

2.为啥是xid-1呢

因为数组或者内存都是索引都是从0开始，计算的时候要这样取

3.为什么需要xid

唯一标识：每个事务有一个唯一的 XID，这允许系统精确地追踪和控制每个独立的操作。
状态管理：通过 XID，系统能够管理每个事务的状态（活动、已提交、已撤销）。这对于处理并发操作和系统故障恢复至关重要。
错误恢复：在系统或硬件故障时，XID 和事务状态可以帮助系统决定哪些事务需要重新执行（例如，所有未提交的事务）。

4.事务状态有哪些

每个事务有三种可能的状态：
- active：事务正在进行中，尚未结束。
- committed：事务已经完成并成功提交。
- aborted：事务已经被撤销或回滚。
这些状态被保存在一个特定的文件（XID 文件）中，每个事务状态占用一个字节的空间。

DM

缓存

由于分页管理和数据项（DataItem）管理都涉及缓存，这里设计一个更通用的缓存框架。三个hashmap

这段代码描述的是一个高级缓存系统，采用引用计数和锁机制来管理缓存项，以适应多线程环境中的数据访问和同步需求。缓存系统由一个抽象类 AbstractCache<T> 实现，该类定义了获取和释放缓存资源的抽象方法，以及实现了资源管理的具体逻辑。这个实现确保了线程安全，并能有效处理资源的加载和释放。以下是代码的详解及其功能：

缓存系统的组件

缓存的数据存储 (cache):
- 用一个 HashMap 存储实际的缓存数据，键是资源的唯一标识符（key），值是资源对象（T）。
资源的引用计数 (references):
- 另一个 HashMap 用于追踪每个资源在缓存中的引用次数。引用计数是管理资源何时可以从缓存中安全移除的重要机制。
正在获取的资源标记 (getting):
- 第三个 HashMap 用于标记那些正被其他线程加载的资源。这防止了对同一资源的多余请求，如果一个资源正在加载中，其他请求该资源的线程会等待，而不是同时尝试加载同一个资源。

缓存操作的流程

获取资源 (get() 方法)

等待其他线程加载资源
- 如果请求的资源正在被其他线程加载（getting 中有记录），当前线程将等待（通过 Thread.sleep），直到资源可用。
直接从缓存中获取
- 如果资源已在缓存中，则直接返回该资源，并将该资源的引用计数增加。
加载新资源

如果资源不在缓存中且缓存未满，标记资源为正在获取（在 getting 中设置标记），然后加载资源。
- 如果加载成功，将资源添加到缓存，并设置引用计数为1。
- 如果加载失败，清除正在获取的标记，并处理异常。

释放资源 (release() 方法)

减少引用计数
- 减少指定资源的引用计数。如果引用计数降至0，则调用 releaseForCache() 方法将资源写回到持久存储（如果有这样的操作），并从缓存中移除该资源。

安全关闭 (close() 方法)

强制回源并清理所有资源
- 在关闭缓存时，遍历所有缓存项，强制释放每个资源，并清理相关数据结构。

缓存的同步和线程安全

通过使用锁（lock.lock() 和 lock.unlock()），上述方法确保在多线程环境下对缓存的访问是线程安全的。锁的使用确保了对缓存结构的修改是互斥的，防止了数据竞争和潜在的并发错误。

总结

这个缓存框架通过抽象方法提供了灵活性，允许定制资源获取和释放的具体逻辑，而通过引用计数和锁机制提供了一种稳健的方法来管理缓存资源的生命周期和并发访问，非常适合需要高并发处理和资源管理的应用场景。

缓存问题

为什么不选择lru？

确实，LRU（Least Recently Used）缓存策略因其简单高效在许多场景中被广泛使用。然而，引用计数策略在特定场景下可能比LRU更合适，特别是在数据库管理系统（DBMS）和其他需要精细控制资源生命周期的系统中。以下是一个例子，详细解释为什么在某些情况下选择引用计数而不是LRU。

场景描述

假设你正在开发一个视频编辑软件，该软件允许用户同时编辑多个视频片段。这些视频片段需要被频繁读取和修改，并且由于视频文件通常很大，因此使用缓存来存储当前正在编辑的片段是很有必要的。

问题出现

如果采用LRU缓存策略，最近最少使用的视频片段将会被自动驱逐出缓存，以便为新的片段腾出空间。考虑以下情形：

编辑工作重叠：用户可能在多个视频片段之间来回切换，对它们进行编辑。使用LRU时，一个长时间未被访问但正处于半编辑状态的视频片段可能会被驱逐。当用户返回这个片段时，他们可能会发现所有未保存的更改都已消失，因为片段被驱逐且更改未被写回磁盘。
资源驱逐时的数据一致性问题：
- 不回源：如果不将修改过的数据写回数据源，那么所有更改都将丢失，这对于需要持久化更改的应用来说是不可接受的。
- 回源：如果每次资源被驱逐时都进行回源操作，这可能导致不必要的I/O开销，特别是当数据并未发生更改时。
- 缓存抖动：频繁地将资源放回缓存并再次被驱逐（因为缓存已满），这会导致所谓的缓存抖动，降低缓存的效率。

引用计数的优势

使用引用计数策略，在这种情况下会更合适：

明确的生命周期控制：每个缓存项的生命周期清晰可控。资源只有在没有任何组件引用它时才会被释放。这为用户提供了一定的安全性，确保正在使用的资源不会被意外驱逐。
减少不必要的写回操作：只有在确定资源不再被需要时才会被驱逐和回源，减少了不必要的磁盘I/O操作。
适应复杂依赖关系：在处理多个相关资源（例如，多个相互依赖的视频片段）时，引用计数可以更好地管理资源之间的依赖关系。

结论

在选择缓存策略时，需要考虑应用的特定需求。虽然LRU提供了一种高效的通用解决方案，但在需要详细管理资源生命周期、防止数据丢失和减少不必要I/O的情况下，引用计数可能是一个更好的选择。在视频编辑软件的场景中，引用计数可以保证用户正在工作的视频片段不会因为缓存策略而意外丢失，提高了应用的稳定性和用户的满意度。

缓存页面

本节主要内容就是 DM 模块向下对文件系统的抽象部分。DM 将文件系统抽象成页面，每次对文件系统的读写都是以页面为单位的。同样，从文件系统读进来的数据也是以页面为单位进行缓存的。

读取磁盘文件为缓存页面类型，插入数据之后，标记页面为脏数据，之后缓存驱逐的时候写入磁盘

在数据库的页面管理系统中，FSO (Free Space Offset) 是用来标识页面内第一个空闲字节的位置。这样设计的目的是为了快速找到可以插入新数据的位置。现在，让我们更详细地解释如何使用 FSO，并以 Page 类为例进行说明。

FSO (Free Space Offset) 详解

初始化 FSO

在 Page 类中，FSO 被初始化为 2。这是因为页面数据的开始两个字节被用来存储 FSO 本身。FSO 是一个 short 类型，占用 2 字节。这意味着：

从字节索引 0 到 1（共2个字节）用于存储表示空闲空间起始位置的 FSO。
FSO 的值为 2 表示从字节索引 2 开始的部分是用于存储实际数据的。

插入数据的过程

插入数据时，Page 类中的 insertData 方法按以下步骤操作：

读取当前 FSO：
- 使用 getFSO 方法读取存储在页面开始的两个字节中的 FSO 值。这个值告诉我们页面中空闲空间的开始位置。
复制新数据到 FSO 指示的位置：
- 使用 System.arraycopy 方法，将新数据从源数组 newData 复制到 Page 的 data 数组中，复制的起始位置是当前的 FSO。
- newData.length 决定了要复制数据的长度。
更新 FSO：
- 插入数据后，新的 FSO 将是原来的 FSO 加上新插入的数据长度 newData.length。这是因为新数据占据了从原 FSO 开始的一段空间。
- 更新后的 FSO 指向下一个空闲的字节，为将来的数据插入做准备。
设置新的 FSO 值：
- 使用 setFSO 方法，将新计算的 FSO 值写回页面数据的开始两个字节中。

如何更新 FSO

setFSO 方法的工作原理如下：

将 short 类型的 FSO 值分解为两个字节。由于 Java 使用大端字节序（高字节优先），offset 的低字节存储在数组的第一个位置，高字节存储在第二个位置。
offset & 0xFF 获取 offset 的低字节。
(offset >> 8) & 0xFF 获取 offset 的高字节。
这两个字节被放回 data 数组的前两个位置，这样 FSO 就更新了。

小结

通过这种方式，Page 类能有效地管理页面内的数据存储和空间分配。初始化 FSO 为 2 是因为要为存储 FSO 本身留出空间。更新 FSO 是为了维护对空闲空间的准确跟踪，确保每次数据插入后，新的空闲空间位置都能被正确记录和使用。这样的设计简化了数据插入操作，提高了数据库系统的效率和性能。

缓存页面问题

如何确定数据库是否正常关闭？

数据库文件的第一页，通常用作一些特殊用途，比如存储一些元数据，用来启动检查什么的。MYDB 的第一页，只是用来做启动检查。具体的原理是，在每次数据库启动时，会生成一串随机字节，存储在 100 ~ 107 字节。在数据库正常关闭时，会将这串字节，拷贝到第一页的 108 ~ 115 字节。

这样数据库在每次启动时，就会检查第一页两处的字节是否相同，以此来判断上一次是否正常关闭。如果是异常关闭，就需要执行数据的恢复流程。

日志

日志读写

日志的二进制文件，按照如下的格式进行排布：

1	[XChecksum][Log1][Log2][Log3]...[LogN][BadTail]

其中 XChecksum 是一个四字节的整数，是对后续所有日志计算的校验和。Log1 ~ LogN 是常规的日志数据，BadTail 是在数据库崩溃时，没有来得及写完的日志数据，这个 BadTail 不一定存在。

每条日志的格式如下：

1	[Size][Checksum][Data]

其中，Size 是一个四字节整数，标识了 Data 段的字节数。Checksum 则是该条日志的校验和。

在打开一个日志文件时，需要首先校验日志文件的 XChecksum，并移除文件尾部可能存在的 BadTail，由于 BadTail 该条日志尚未写入完成，文件的校验和也就不会包含该日志的校验和，去掉 BadTail 即可保证日志文件的一致性。

向日志文件写入日志时，也是首先将数据包裹成日志格式，写入文件后，再更新文件的校验和，更新校验和时，会刷新缓冲区，保证内容写入磁盘。

恢复策略

多线程

经过以上的操作，就能保证了 MYDB 在单线程下的恢复性。对于多线程的情况下呢？我们来考虑下面的两种情况。

第一种：

T1 begin
T2 begin
T2 U(x)
T1 R(x)
...
T1 commit
MYDB break down

在系统崩溃时，T2 仍然是活跃状态。那么当数据库重新启动，执行恢复例程时，会撤销 T2，它对数据库的影响会被消除。但是由于 T1 读取了 T2 更新的值，既然 T2 被撤销，那么 T1 也应当被撤销。这种情况，就是级联回滚。但是，T1 已经 commit 了，所有 commit 的事务的影响，应当被持久化。这里就造成了矛盾。所以这里需要保证：

规定1：正在进行的事务，不会读取其他任何未提交的事务产生的数据。

第二种情况，假设 x 的初值是 0

T1 begin
T2 begin
T1 set x = x+1 // 产生的日志为(T1, U, A, 0, 1)
T2 set x = x+1 // 产生的日志为(T1, U, A, 1, 2)
T2 commit
MYDB break down

在系统崩溃时，T1 仍然是活跃状态。那么当数据库重新启动，执行恢复例程时，会对 T1 进行撤销，对 T2 进行重做，但是，无论撤销和重做的先后顺序如何，x 最后的结果，要么是 0，要么是 2，这都是错误的。

出现这种问题的原因, 归根结底是因为我们的日志太过简单, 仅仅记录了”前相”和”后相”. 并单纯的依靠”前相”undo, 依靠”后相”redo. 这种简单的日志方式和恢复方式, 并不能涵盖住所有数据库操作形成的语义

解决方法有两种：

增加日志种类
限制数据库操作

MYDB 采用的是限制数据库操作，需要保证：

规定2：正在进行的事务，不会修改其他任何未提交的事务修改或产生的数据。

vm 没有删除？
vm解决保证规定执行

页面索引

页面索引，缓存了每一页的空闲空间。用于在上层模块进行插入操作时，能够快速找到一个合适空间的页面，而无需从磁盘或者缓存中检查每一个页面的信息。

MYDB 用一个比较粗略的算法实现了页面索引，将一页的空间划分成了 40 个区间。在启动时，就会遍历所有的页面信息，获取页面的空闲空间，安排到这 40 个区间中。insert 在请求一个页时，会首先将所需的空间向上取整，映射到某一个区间，随后取出这个区间的任何一页，都可以满足需求。

DataItem 中保存的数据，结构如下：

1	[ValidFlag] [DataSize] [Data]

其中 ValidFlag 占用 1 字节，标识了该 DataItem 是否有效。删除一个 DataItem，只需要简单地将其有效位设置为 0。DataSize 占用 2 字节，标识了后面 Data 的长度。

DataManager 是 DM 层直接对外提供方法的类，同时，也实现成 DataItem 对象的缓存。DataItem 存储的 key，是由页号和页内偏移组成的一个 8 字节无符号整数，页号和偏移各占 4 字节。

DataItem 缓存，getForCache()，只需要从 key 中解析出页号，从 pageCache 中获取到页面，再根据偏移，解析出 DataItem 即可：

VM

那么这样，对同一个数据操作的冲突，其实就只有下面这两种情况：

两个不同事务的 U 操作冲突
两个不同事务的 U、R 操作冲突

那么冲突或者不冲突，意义何在？作用在于，交换两个互不冲突的操作的顺序，不会对最终的结果造成影响，而交换两个冲突操作的顺序，则是会有影响的。

现在我们先抛开冲突不谈，记得在第四章举的例子吗，在并发情况下，两个事务同时操作 x。假设 x 的初值是 0：

T1 begin
T2 begin
R1(x) // T1读到0
R2(x) // T2读到0
U1(0+1) // T1尝试把x+1
U2(0+1) // T2尝试把x+1
T1 commit
T2 commit

由于同时读取最后 x 的结果是 1，这个结果显然与期望的不符。

MVCC和2PL_可重复度和执行串行化

VM 的一个很重要的职责，就是实现了调度序列的可串行化。MYDB 采用两段锁协议（2PL）来实现。当采用 2PL 时，如果某个事务 i 已经对 x 加锁，且另一个事务 j 也想操作 x，但是这个操作与事务 i 之前的操作相互冲突的话，事务 j 就会被阻塞。譬如，T1 已经因为 U1(x) 锁定了 x，那么 T2 对 x 的读或者写操作都会被阻塞，T2 必须等待 T1 释放掉对 x 的锁。

由此来看，2PL 确实保证了调度序列的可串行话，但是不可避免地导致了事务间的相互阻塞，甚至可能导致死锁。MYDB 为了提高事务处理的效率，降低阻塞概率，实现了 MVCC。

对于一条记录来说，MYDB 使用 Entry 类维护了其结构。虽然理论上，MVCC 实现了多版本，但是在实现中，VM 并没有提供 Update 操作，对于字段的更新操作由后面的表和字段管理（TBM）实现。所以在 VM 的实现中，一条记录只有一个版本。

一条记录存储在一条 Data Item 中，所以 Entry 中保存一个 DataItem 的引用即可：

我们规定，一条 Entry 中存储的数据格式如下：

1	[XMIN] [XMAX] [DATA]

XMIN 是创建该条记录（版本）的事务编号，而 XMAX 则是删除该条记录（版本）的事务编号。它们的作用将在下一节中说明。DATA 就是这条记录持有的数据。

可重复读

不可重复度，会导致一个事务在执行期间对同一个数据项的读取得到不同结果。如下面的结果，加入 X 初始值为 0：

T1 begin
R1(X) // T1 读得 0
T2 begin
U2(X) // 将 X 修改为 1
T2 commit
R1(X) // T1 读的 1

可以看到，T1 两次读 X，读到的结果不一样。如果想要避免这个情况，就需要引入更严格的隔离级别，即可重复读（repeatable read）。

T1 在第二次读取的时候，读到了已经提交的 T2 修改的值，导致了这个问题。于是我们可以规定：

事务只能读取它开始时, 就已经结束的那些事务产生的数据版本

这条规定，增加于，事务需要忽略：

在本事务后开始的事务的数据;
本事务开始时还是 active 状态的事务的数据

对于第一条，只需要比较事务 ID，即可确定。而对于第二条，则需要在事务 Ti 开始时，记录下当前活跃的所有事务 SP(Ti)，如果记录的某个版本，XMIN 在 SP(Ti) 中，也应当对 Ti 不可见。

死锁解决

上一节提到了 2PL 会阻塞事务，直至持有锁的线程释放锁。可以将这种等待关系抽象成有向边，例如 Tj 在等待 Ti，就可以表示为 Tj –> Ti。这样，无数有向边就可以形成一个图（不一定是连通图）。检测死锁也就简单了，只需要查看这个图中是否有环即可。

MYDB 使用一个 LockTable 对象，在内存中维护这张图。维护结构如下：

public class LockTable {

    private Map<Long, List<Long>> x2u;  // 某个XID已经获得的资源的UID列表
    private Map<Long, Long> u2x;        // UID被某个XID持有
    private Map<Long, List<Long>> wait; // 正在等待UID的XID列表
    private Map<Long, Lock> waitLock;   // 正在等待资源的XID的锁
    private Map<Long, Long> waitU;      // XID正在等待的UID
    private Lock lock;

    ...
}

Copy

在每次出现等待的情况时，就尝试向图中增加一条边，并进行死锁检测。如果检测到死锁，就撤销这条边，不允许添加，并撤销该事务。

VM和DM，IM的关系

数据操作和传输的互动

事务开始时：
- 当一个事务开始时，TM 创建一个事务上下文（包括事务ID和其他元数据），并将其标记为活动状态。
- VM 在开始事务时，为这个事务准备一个快照，以支持MVCC，允许事务看到一致的数据视图。
数据读取：
- 当事务请求读取数据时，VM 首先会查询 TM 确定当前事务的隔离级别和可见性。
- VM 使用TM提供的信息来决定哪个版本的数据对当前事务可见，并从 DM 请求读取相应版本的数据。
- DM 从物理存储中检索数据并返回给 VM，VM 然后再将数据返回给请求的事务。
数据写入：
- 写操作首先由 VM 接收，它记录要修改的数据版本。
- VM 可能需要与 TM 协商获取必要的锁，以防止其他并发事务对相同数据的干扰。
- 数据的新版本被写入前，先在 DM 中创建，包括所有必要的日志信息，以便在发生故障时能够恢复。
- 完成写操作后，VM 会更新数据版本，并在事务提交时通知 TM。
事务提交和回滚：
- 当事务准备提交时，TM 检查所有操作是否成功，并指示 VM 和 DM 提交或回滚所有更改。
- 如果事务提交，VM 更新版本控制信息，并确认更改永久保存在 DM。
- 如果事务需要回滚，VM 指示 DM 撤销所有未提交的写操作，并恢复数据到事务开始前的状态。

IM

IM，即 Index Manager，索引管理器，为 MYDB 提供了基于 B+ 树的聚簇索引。目前 MYDB 只支持基于索引查找数据，不支持全表扫描。感兴趣的同学可以自行实现。

在依赖关系图中可以看到，IM 直接基于 DM，而没有基于 VM。索引的数据被直接插入数据库文件中，而不需要经过版本管理。

二叉树由一个个 Node 组成，每个 Node 都存储在一条 DataItem 中。结构如下：

1 2	[LeafFlag][KeyNumber][SiblingUid] [Son0][Key0][Son1][Key1]...[SonN][KeyN]

其中 LeafFlag 标记了该节点是否是个叶子节点；KeyNumber 为该节点中 key 的个数；SiblingUid 是其兄弟节点存储在 DM 中的 UID（通常是sonN+1，保证连续）。

LeafFlag = 0 (非叶子节点)

KeyNumber = 3

SiblingUid = 102

Son0 = 100, Key0 = 15, Son1 = 101, Key1 = 30, Son2 = 103, Key2 = Long.MAX_VALUE

这表示当前节点有三个键（15, 30, MAX_VALUE）和四个子节点（UID分别为100, 101, 103, 和对应的下一个兄弟节点102）。

后续是穿插的子节点（SonN）和 KeyN。最后的一个 KeyN 始终为 MAX_VALUE，以此方便查找。key0是0-key0的范围

Node 类持有了其 B+ 树结构的引用，DataItem 的引用和 SubArray 的引用，用于方便快速修改数据和释放数据。

public class Node {
    BPlusTree tree;
    DataItem dataItem;
    SubArray raw;
    long uid;
    ...
}

DM和IM的关系

DM（数据管理）

在这个上下文中，DM指的是负责存储和管理实际数据的组件。在B+树实现中，每个节点的数据（包括键和指向子节点的指针）通常存储在持久化存储介质上，DM负责这部分数据的读写操作。DataItem是一个抽象，它代表存储在DM中的一块数据。

数据的读取：当Node需要被加载时，使用DM的read方法通过节点的唯一标识符（UID）来获取对应的DataItem。例如，loadNode方法在Node类中用于根据UID加载节点，这包括从DM中读取数据并解析为Node的内部表示。
数据的写入：当节点数据需要更新或新增时，DM同样负责写入这些更改。例如，在节点分裂时，新节点的数据需要被写入存储系统，这通过DM的insert方法完成，它返回新节点的UID。

IM（索引管理）

IM则是管理索引的部分，主要负责使用这些数据项（DataItem）来维护和更新索引结构。在这个Java类实现中，Node类本身可以视为IM的一部分，因为它直接处理与索引相关的所有逻辑，包括搜索、插入和分割等操作。

数据的添加和获取

添加数据：
- 插入新键或新子节点时，例如insertAndSplit方法中，Node首先计算插入位置，然后调整现有的键和子节点UIDs，必要时进行节点分裂，并将更改写回到DM。
获取数据：
- 当需要找到一个键对应的子节点时，searchNext方法被调用。这个方法通过比较节点中存储的键来确定应该访问的子节点的UID。
- leafSearchRange方法用于执行范围搜索，它返回一个键范围内的所有相关子节点的UID列表。

IM 对上层模块主要提供两种能力：插入索引和搜索节点。向 B+ 树插入节点和搜索节点的算法和实现，不再赘述。

这里可能会有疑问，IM 为什么不提供删除索引的能力。当上层模块通过 VM 删除某个 Entry，实际的操作是设置其 XMAX。

TBM

解析器

这个 Tokenizer 类是一个文本解析器，主要用于从一个字节流（例如字符串的字节表示）中提取语义上有意义的标记（tokens）。该解析器能够处理空白字符、标点符号、引号包裹的字符串以及字母数字组成的词。这样的解析器常见于编程语言的编译器、解释器或任何需要从文本输入中提取信息的软件中。

使用Parser类来对获取到的对应字段进行操作解析对应的语句
最后返回定义的参数

TBM和IM和VM的关系

表的创建和管理：
- 当 TBM 创建新表时，它将表的定义（包括表名和字段信息等）存储在 VM 中。这通常涉及编码表的结构到一个字节流中，并将这个字节流保存在持久化存储中。
- 如果表的字段具有索引，TBM 将调用 IM 来创建这些索引。索引的创建包括确定索引的类型（如 B+树），并将索引的根存储在字段定义中。
数据查询和修改：
- 当执行查询（如 SELECT）时，TBM 可能需要利用 IM 提供的索引来快速定位数据。这涉及到读取字段的索引信息，并通过索引快速找到数据的存储位置。
- 更新或删除操作可能需要修改索引结构，这时 TBM 将指导 IM 调整索引以反映数据的变更。

CS/BS

在您的系统中，Server 和 Client 分别扮演数据库服务提供者和消费者的角色。他们通过使用 Java 套接字（Socket）进行通信，实现命令的发送和数据的接收。这里的实现借助几个关键类：Packager，Transporter，和 Encoder，以及两个入口类 Launcher 用于启动服务器和客户端。下面我将详细解释这些组件的作用和数据传输过程，并给出一个具体的使用例子。

Server 的作用和实现

作用：

监听一个端口，接收来自客户端的连接请求。
对每个客户端请求，创建一个新线程（通过 ClientHandler 类）来处理。
解析客户端发送的 SQL 命令，执行这些命令，并将结果返回给客户端。

实现：

Server 类使用 ServerSocket 来监听指定端口的连接请求。一旦有客户端连接，就创建一个新线程来处理该连接。
在处理线程中（ClientHandler），通过 Packager 类来接收和发送数据包（Package）。

Client 的作用和实现

作用：

连接到服务器。
发送 SQL 命令到服务器，并接收执行结果。

实现：

Client 类通过套接字连接到服务器，并使用 Packager 来发送和接收数据包。
提供 execute 方法来发送 SQL 命令并接收结果。

数据传输

编码和发送：
- 客户端通过 Encoder 类将 SQL 命令编码为二进制数据，封装在 Package 对象中。
- Packager 类通过 Transporter 将数据包发送出去。数据在发送前会被转换为十六进制字符串以避免特殊字符问题，并通过套接字发送。
接收和解码：
- 服务器接收到数据后，通过 Transporter 读取数据，然后使用 Encoder 解码。
- 解码后的数据包含 SQL 命令，服务器执行这些命令，并将结果（或错误信息）再次通过 Encoder 编码后返回给客户端。