数据结构实现

vector

• 工程经验1：为什么不使用new和delete而是使用分配器allocate、deallocate和helper.template construct、helper.template destroy？

new事实上是分配内存和调用对象的构造函数（如果没有传参就直接调用默认构造函数）
那么这样来看分配器的优势在于：（1）降低系统设计的耦合性，允许更加精细的控制（2）模板类型可能是一个没有默认构造函数的类，这种情况使用new会导致报错
（解决方案一个是使用分配器，另一个是在vector中存放指向数据的指针而不是数据本身，对于这个项目使用的是分配器的实现）

• 工程经验:关于内存泄露：

（1）如何检测到内存泄漏的存在：Linux下可以使用valgrind工具，例如valgrind --leak-check=full ./your_program，具体参加官方文档
（2）如何在编码过程中尽可能避免内存泄漏的出现：（a）良好的编码习惯，先分析好哪些函数有可能涉及到堆空间的申请以及释放，可以在函数内部加上注释说明。注意”成双成对“原则，比如构造函数中new，析构函数中delete
（b）封装一个中间层来让他管理，这里有现成可以调用的库：使用智能指针，比如shared_ptr，unique_ptr，weak_ptr，这样可以避免手动管理内存的麻烦，不过shared_ptr会有循环引用的问题，需要排查这种可能，出现的话需要使用weak_ptr打破循环引用

• 注意点1：实现了两个at:T & at(const size_t &pos);const T & at(const size_t &pos) const;什么时候调用哪一个？

当对于const对象（包括const指针，const引用）用const版本的at，否则用非const版本的at
注意只和vector对象的const属性有关，比如vector<int> v; const int &tmp = v1.at(0);还是调用的是非const版本的at

• 注意点2：at和[]的区别？

在STL中，两者是有区别的，at是有范围检查的，错误时会抛出错误；而[]没有范围检查。这导致了两者性能的区别
不过这个项目中，两者的实现都带有范围检查。

map

• 工程经验1：为什么在node的析构函数中选择释放所有资源之后还将其置为nullptr?

从正确性上来说并不必要，且还有一定时间开销，但是这样可以帮助在调试时更容易发现悬空指针问题，对于调式阶段更友好。

• 工程经验2：既然node内部存的是指针，那么为什么构造函数中传参为什么不直接用指针而是用值传递？

指针作为参数的风险：
（1）悬挂指针（Dangling Pointer）：如果传入的指针指向的对象在构造函数外部被释放，构造函数内部仍然使用该指针，会导致未定义行为。
（2）所有权不明确：指针传递无法明确指针的所有权（谁负责释放内存），容易导致内存泄漏或重复释放。
这里值传递更直观、安全，是现代 C++ 推荐的实践。

• 工程经验3：对于类中的工具函数，比如leftNode，良好的代码规范应该是用static修饰、并放在private中

• 工程经验4：copy函数的实现注意要正确维护父亲信息。

• 实现信息

插入和删除都是实现的自底向上的做法

对于空节点的处理：参照算法导论的做法引入NIL，即代码中的markNode

linkedHashMap

• 实现信息

（1）哈希表使用的是开散列表，没有动态扩容，容量超过maxSize就会del最近最少使用的元素
（2）双向链表的cur是dummy头节点，beg是存了实际数据的尾节点，这种实现不美观，不如全都用dummy节点

• 工程经验1：delTime()中出现的惊天bug

delTime中一开始没有p->timeNext = p->timePre = nullptr;想着节点都被删掉了不需要维护p的信息，但是事实上对于delTime的调用情景有可能是在modifyTime，
此时没有删除p，所以p的信息是需要维护的。

这个bug浪费了三个小时，总结出来的教训如下：
（1）重视单元测试：当时觉得这一块不会写出bug，所以写完之后没有自己进行任何测试，正确的做法应该是写一个测试程序，一切无误之后才将其使用在后续的程序中
（2）书写函数的时候不能想当然给函数的调用情形有不正确的预设。要仔细考虑系统中所有函数的调用关系图谱，另外如果代码后续还要往上加功能维护的话，建议写一个文档或者注释说明函数的调用情形（或者调用场景的预设）

BPT

• 相关知识

设计到外部存储的数据结构设计时，需要先充分了解外部存储的特性：

（1）磁盘IO速度和内存内的操作相比很慢，减少IO次数是首要矛盾
（2）磁盘的顺序访问远快于随机访问，设计数据结构尽量利用顺序访问优势
（3）磁盘的读写单位是块而不是单个字节，设计数据结构时要考虑磁盘块的大小

B树和B+树定义不再赘述，两者的核心设计区别在于B树的非叶子节点也存储数据，而B+树的非叶子节点只存储索引，只有叶子节点才存储数据块的地址索引；
且B+树的叶子节点之间有链表相连。由此可以导出若干对比

B+树的优势：
（1）在处理范围查询或者全表扫描的时候，B+树远快于B树
（2）B+树所有数据的高度都是一样的，查询性能更加稳定
（3）由于B+树中不存储data，因此可以存储更多的索引，使得B+树的层次更少

B树的优势：
（1）在处理点查询（精确查找）场景下，B树快于B+树
（2）点查询性能有波动其实可以换一个角度思考：这样的不对等性相当于一种天然的“缓存”可以帮助我们去优化不对等的数据查询的平均开销。我们可以做一些优化，”通常90%的访问都是针对10%的数据“把频繁访问的数据放在靠近根节点的位置

• BPT的文件系统协议说明

代码中主数据文件是dataBase，文件中第一个int是根节点在文件中的位置，后面是若干个node，其关联的文件负责存储 B+树的核心数据，并在 B+树的构造和析构过程中确保数据的持久化
recycle是回收站，对应的内存中的vacancy这个vector对象。文件中首先是一个int记录有多少个记录，之后是若干个int记录空缺位置的起点（长度均默认为node的大小）。后续新建节点的时候优先在vacancy中找，这样防止空泡的产生，避免空间浪费
BPT的析构函数中：首先是对于recycle的持久化，我们用vacancy对于recycle进行write-back，然后用map对于dataBase进行write-back，并更新dataBase的根节点位置

这里建立了一个抽象，readNode和writeNode，对应了找内存中的缓存和去文件中找的过程

• BPT接口说明

find支持同一个key有多个value的情况，返回的是一个vector,这样做是因为后续要通过user映射到订单
支持delete。因为后续会有delete_train

• split实现说明

往下走找key的时候用的二分

最先实现的 split 函数用于在 B+ 树中分裂节点 a，主要分为五个逻辑步骤。（1）首先，尝试找到节点 a 的父节点 b：如果 a 是根节点，则创建一个新的根节点 b 并更新 a 的父指针；否则，从磁盘读取 a 的父节点 b。
（2）接着，初始化新节点 c，将 a 的一半键和子节点分配给 c，更新 a 和 c 的属性（如 cnt 和 next），如果a不是叶节点，还需要分别去写a的一半的儿子的父指针。
（3）更新父节点 b 的key以及cnt。之后，然后更新后的节点 a、b 和 c 写回磁盘。（4）最后，检查父节点 b 是否超过容量，若超过则递归调用 split 进行进一步分裂。

问题在于由于需要维护每个节点的父节点信息，分裂时需更新 c 的所有子节点的父指针，导致大量磁盘 I/O 操作，影响性能。
改进方案的核心是避免显式维护父节点信息。通过在插入、删除等操作中自顶向下遍历时记录路径（刚好用自己写的vector就可以），可以在分裂时直接通过路径找到父节点并更新其信息，而无需更新子节点的父指针。
注：乍一看以为时间复杂度最坏都是O(m log_{m}(n))，m是节点的大小，n是节点的数量,只是维护父节点信息的话常数翻了一倍
但是仔细一想这里访问磁盘的操作应该是主导性的，未优化的话内存操作O（m），访问磁盘O（m），所以这里的时间复杂度应该是O（m log_{m}(n)）
而优化之后，内存操作O（m），访问磁盘O（1），时间复杂度应该是O（log_{m}(n)），不只是常数优化！

通过这个分析，我们在接触访问外存的时候应该时刻记住，访问外存的时间复杂度是主导性的，内存操作的时间复杂度是次要的

• merge实现说明

会尝试从兄弟节点借用键或与兄弟节点合并。如果合并则父节点key减少，需要检查并可能导致递归merge。整个过程同样涉及到读取一半节点维护其父亲节点。

• 工程经验1：关于BPT节点的定义，ch开的大小是M + 2，虽然最多的情况是M + 1，但是过渡态有可能达到M + 2

主程序实现逻辑

主要的对象

• 自然的：user、train、order
• 抽象出来的：trainStation

这里trainStation和现实意义上的车站不是同一个涵义，其是一个关联到车的时空对象，整体来说关联了如下信息
关于train：trainID、fileID、saleDatBegin、saleDateEnd
关于车自身：和前一站之间的票价，到达时间、停靠时间、kth站
这样设计是为了后面查询票价、换乘等操作不必使用O(N^2)数量的对象而只需要O(N)

涉及到的BPT数据结构

• str->int->user对象 sjtu::BPlusTree<diyString, int> userDataBase;
• trainID str->size_t->int->train对象 sjtu::BPlusTree<size_t, int> trainDataBase;
• stationID str->size_t->trainStation对象 sjtu::BPlusTree<size_t, int> stationDataBase;
• str->size_t->order对象 sjtu::BPlusTree<size_t, int> orderDataBase;

其中存储trainStation和order的直接放进BPT的原因是想要取出来的数据是有序的，这里trainStation的 排序是按照trainID来进行的，order的排序是按照time来进行的

部分函数实现

release_train

O(N) 添加station对象，这样规避了需要加入O(N^2)个对象，其中N为车站数目，这样的设计优越性我们会在后面看到

query_ticket

1. 通过起始站和终点站的str在stationDataBase中找到对应的候选trainStation对象，由于BPT的有序性，这里的station对象关联的trainID是有序的
2. 我们需要先确保两个trainStation对象的trainID是一样的，根据trainID有序性，这里只需要双指针即可，是线性的
3. 进一步判断，起始站和站点站的kth关系，以及对应的saleDate是否合法
4. 符合条件的进入vec，然后按照所需时间或者票价从小到大排序 （注意：由于query_ticket是高频被调用的，所以抽象出来trainStation帮助加速，并使用双指针）

query_transfer

1. 最开始的实现：第一层枚举经过起点站的火车 (A)，第二层枚举经过终点站的火车 (B)，第三层枚举火车 (A) 的所有可能中转站 (G)，第四层枚举火车 (B) 的所有站点以检查是否经过 (G)。 (O(N^4))
2. 实际的实现：第一、二层枚举经过起点站的火车 (A) 和中转站 (G)，内层先找通过G的所有火车的trainID，然后使用双指针法过滤出同时经过终点站的火车。(O(N^3))
3. 发现可以进一步做的优化：第一、二层枚举经过起点站的火车 (A) 和中转站 (G)，内层直接(O(1))\哈希找到从G到终点站的trainID。这里需要预处理，枚举所有经过终点的trainID B，枚举B的每个站点X，将X->B写入哈希表。(O(N^2))

query_order

直接查找即可，且sjtu::BPlusTree<size_t, int> orderDataBase;天然就是已经排好序的了

refund_ticket

• 朴素观察：虽然候补序列可能很繁杂，但是当前退票只可能影响哪些涉及到这个车次的候补，所以我们不应该是遍历所有候补，而是通过车次去找到该车次关联的候补
• 数据结构：首先因为给定一个order要支持删除，所以我们应该要提供一个timestamp->order fileID的BPT(waitingDataBase)，这里用timestamp作为标识也是为了后面trainWaitingDataBase取出来是有序的，然后用文件来做从fileID到具体Order的映射，其实至此这两个数据结构就已经提供足够多的数据可以做了。 但是由于要支持上面的车次映射，所以再加了一层trainID->timestamp的BPT(trainWaitingDataBase)
• 具体流程如下：

1. 流程合法检查通过之后，我们可以拿到当前这个order的timestamp和trainID，我们直接去两个BPT里面把这个order删掉
2. 然后我们对于这个order关联的trainID找到所有的timestamp（这是一个一步的查询，注意由于这里是有序的，所以取出来的timestamp就天然有序了）
3. 然后去waitingDataBase找到所有的order fileID（范围查询，BPT擅长的）
4. 把order依次读出来，然后检查是否满足购票要求，这是一个老老实实的遍历

• 一些进一步思考：如果火车关联的候补很多，上面还是要遍历，有没有办法优化，即有没有办法不需要遍历完所有的候补？

1. 考虑一个一维的情形，火车只有起点和终点，那么最先想到的就是单调栈加二分
2. 但是首先单调栈需要在中间维护，如果使用序列化容器来装的话移动成本可能比较高，又不是序列化但是又支持二分，想到的是跳表。另外这里并不是一维情形，设计算法难度较大，最终就没有往下继续做。

（因为timestamp->order fileID是保序的且BPT会排序，所以取出来都是按照timestamp从小到大满足要求）

存一个trainID->OrderID的哈希

一些优化设计

• 为什么BPT（比如一个存train的BPT）中存储的value，不是train在记录文件中的实际位置，而是存一个编号然后去乘sizeof来得到实际位置？

其实最开始只是直觉上觉得不要写死更好，后面仔细想有这样的优越性：
（1）BPT中ch数组数据对象占用空间更小，在磁盘一个块大小不变的情况下，BPT的阶数更大，树的高度可以更加低，以访问外存为主导的查询效率更高。这里很有意思的省空间就是省时间。
2字节的unsigned short 可以到65535.可以很好地cover住train的数目了（order的可以不行），但是如果存实际位置的话，sizeof(train)就6k了，只能10辆火车，炸裂
（2）提供了一个抽象层次，将BPT和记录文件解耦，可维护性和可扩展性可能更好。举一个例子，如果后面需要更换记录文件中对象的大小（比如目前每个火车最多经过20站，未来要扩展到200站），那么sizeof(train)就要变化，那么整个BPT要全部改动

• 以train的BPT为例，为什么不直接str映射到value，而是先strHash将str映射到一个size_t然后再用BPT将这个size_t映射到train对象在记录文件中的编号？

其实和之前的原因是一样的，让BPT中每一个node要存一串key和一串value，除了减少单个value的数据类型大小，我们也可以优化key。比如如果车次名字字符长度上限是40，这里用strHash的优势就体现出来了。
另外注意strHash用的是跨运行也保持一致的，所以可以正常work

• 逻辑上一个车次在不同日期不同地点下的余票是关联到车次对象的，所以自然的实现是把这个信息封装到车次中。为什么不这么做？

主要目的是节约文件读写的问题。一般来说写回的数据至多修改余票的信息，如果整个封装在一起事实上很多写回的操作是没有必要的。
用一组数据说话，拆分后：
sizeof(train)是6k sizeof(seat_Train)是40k, sizeof(seat_DateAndTrain)是0.4k。以磁盘块大小是4k,那么优化之前每次修改余票信息要涉及到12个块，现在只需要1个块，对于修改余量这个最高频率的操作，耗时优化到原来10%