DBMS

Todo

• 表的建立(简单指明列类型)
• 对表的增删查改
• 索引的建立和删除
• 对前端语法解析器的优化
• 使用索引去查找行(包括覆盖索引)
• 存储文件的优化(参照InnoDB)
• 对各种字段类型的处理, 可扩展字段

目录结构

• src
  • index_tree
    • col_types
      • col_type_interface.cpp
      • col_type_interface.h
      • int.cpp
      • int.h
      • string.cpp
      • string.h
    • b_plus_tree.h
    • index.cpp
    • index.h
  • CMakeLists.txt
  • main.cpp
• tests
  • CMakeLists.txt
  • common.cpp
  • common.h
  • test_b_plus_tree.cpp
  • test_create_table.cpp.backup
  • test_example.cpp
  • test_file.cpp.backup
  • test_index.cpp
  • test_index_tree.cpp
  • test_table.cpp.backup
  • test_template.cpp
• CMakeLists.txt

---

思路

1. 表存储:

假设我们有个表名为student,其存储结构如下

STUDENT
├── STUDENT.frm
├── STUDENT.idb
├── index_name1.index
└── index_name2.index
    .....

其中表名.frm是表结构, 表名.idb是行数据, 索引名.index是索引文件.

2. 索引树/B+树

2.1 索引的实现

考虑mysql的索引是可以多列且字段也是任意的类型(数字,字符串等等). 所以这里我使用了 c++的多态特性, 即利用一个基类ColTypeInterface, 然后定义纯虚函数, 纯虚函数主要实现 该类型的各种比较操作,方便后续b+树的索引比较,所有自定义的列类型必须继承ColTypeInterface, 然后重写纯虚函数.

ps: 这里本来是想把比较函数定义为纯虚函数,如

virtual friend bool operator>=(const ColTypeInterface &i1, const ColTypeInterface &i2) = 0;, 然后发现C++不支持, google了下, 发现只要简单的重写比较函数, 然后调用其自定义的纯虚函数即可.

bool operator<(const ColTypeInterface &i1, const ColTypeInterface &i2) {
    return i1.less(const_cast<ColTypeInterface *>(&i1), const_cast<ColTypeInterface *>(&i2));
}

virtual bool less(ColTypeInterface *p1, ColTypeInterface *p2) const = 0; // 派生类重写即可

自定义各种列类型之后,就要考虑有个结构能够把各种不同的列包含进来, 并实现各种比较,这里我采用的是 一个Index类(注意其基类), 实现Index的各种比较方法

class Index : public std::vector<ColTypeInterface *>{
public:
    Index();

    friend bool operator<(const Index &i1, const Index &i2);

    friend bool operator==(const Index &i1, const Index &i2);

    friend bool operator>(const Index &i1, const Index &i2);

    friend bool operator>=(const Index &i1, const Index &i2);

    friend bool operator<=(const Index &i1, const Index &i2);

    friend std::ostream &operator<<(std::ostream &os, Index const &data);
};

具体用法可以参见 test_index.cpp

2.2 Mysql的InnoDB引擎是使用B+树作为索引树,

• 对于主索引来说, 叶节点是存放具体行数据, 对于非叶子节点来说, 不存放数据,只 存放主键内容
• 对于第二索引(index)来说, 叶节点存放的是主键, 非叶子节点存放索引内容

2.3 B+树的实现

代码参考: b_plus_tree.h

思路参考: B树和B+树的插入、删除图文详解 - nullzx - 博客园

用法参考: test_b_plus_tree.cpp (待完善)

B+树的实现是真的很恶心. 我写了好几天才写出来, 而且还不是那么完善. 有兴趣的可以研究下代码

3. 如何控制不同表?

不考虑多库的情况下, 对于一个库, 可能有多个表, 那么如何控制多个表呢?

这里的实现的一个Table是操作一个表的, 通过初始化时传入的表名参数来决定是控制 哪个表, 而DB类内有一个map来存放Table *, 当要使用表时, 动态生成Table实例, 并加入map中. 不需要的话直接从map去除就好了

参考链接/书籍

• MySQL技术内幕(InnoDB存储引擎)
• InnoDB 存储引擎体系架构 - ygmyth - SegmentFault 思否
• MySQL探秘(三):InnoDB的内存结构和特性 - remCarpediem的Android探索之旅 - SegmentFault 思否
• B树和B+树的插入、删除图文详解 - nullzx - 博客园