/TrainTicketSystem

ACM 2022 DataStructure Homework Final!

Primary LanguageJavaScript

Train-Ticket-System

ACM 2022 Data-Structure Homework Final!

历时不知道多少天，终于通过OJ数据啦！

前端也完全搞定啦！

组内分工：

逻辑、前后端交互：尹良升

B+树、前端静态：董珅

各分支用途：

  • master 用于每一个大版本的发布
  • frontend前端的所有文件上传完毕
  • dev_yls 在没有bptree的时候，用map代替bptree的调试分支
  • dev_ds B+树以及外存部分的开发分支，完全由董珅管理。
  • test 用于合并dev_ds以及代码的调试
  • test_output_directly 将vector<std::string>格式的代码输出改成直接输出，后合并至test
  • test_cached_in_function 将query_transfer的缓存改在函数内（为了卡常数），会爆内存，后舍弃
  • test_rollback 加了一个外存分块栈，用于记录回滚信息，已合并至master

缓存的实现机制：

  • 对bptree的find操作，modify操作进行缓存。
  • 用一个闭散列表来实现，有冲突时直接下放到外存。
  • 发生修改的元素使用链表连接，在bptree中执行lower_bound操作时，先遍历链表执行flush操作。

回滚的实现机制：

  • 每一颗bptree用一个外存的栈来记录操作。
  • 外存的栈同样采用分块的形式，对象中自带一个大小约为4096的块进行缓存。

特别鸣谢：

  • 感谢wennitao、pks、RainyMemory三位课程助教对我们组的帮助。
  • 感谢董易昕学长、洪熠佳学长在卡常上的帮助。
  • 感谢郭俊贤、范棋珈、冯悦洋、梁亚伦、刘祎禹、王俞皓等同学在后端实现过程中的帮助。
  • ......