Posts

TABLE INDEX A table index is a replica of a subset of a table’s attributes that are organized and/or sorted for efficient access using those attributes.The DBMS ensures that the contents of the table and the index are logically synchronized. 索引让数据在数据库中的查询更加的高效，DBMS负责使索引和实际内容同步。 DBMS的工作是选择最优的索引去执行查询，这就带来一个需要权衡的问题——索引越多查询越高效但是相对的维护成本（Maintenance Overhead）和存储成本（Storage Overhead） 就会相应的提高。 B-TREE FAMILY B-树家族。 重点了解B+树。 （B树虽然是一个平衡树（balance），但B树的B不是balance的缩写，到底代表什么还存疑） B+TREE B+树是一个自平衡树的数据结构，顺序的存储数据，并且将查询，顺序访问，插入和删除的时间复杂度基本控制在O(log n)。 是二叉搜索树的推广，因为它可以有超过两个的孩子节点。 它针对系统和存储之间的大块数据读写进行了特别的优化。 B+TREE PROPERTIES B+树是一个多叉搜索树，有以下特性： 他完美平衡 除了根节点都至少半满 k个值会把一个节点分为k+1部分。 B+TREE EXAMPLE 上图是一个小例子，能够发现B+树底层是能够双向访问的，这在多线程的时候有可能会造成死锁问题。这在后面讲解B+树多线程的章节也会对原因进行讲解。 ...

CMU15-445 作为 CMU 数据库的入门课，这门课由数据库领域的大牛 Andy Pavlo 讲授（“这个世界上我只在乎两件事，一是我的老婆，二就是数据库”）。 这是一门质量极高，资源极齐全的 Database 入门课，这门课的 Faculty 和背后的 CMU Database Group 将课程对应的基础设施 (Autograder, Discord) 和课程资料 (Lectures, Notes, Homework) 完全开源，让每一个愿意学习数据库的同学都可以享受到几乎等同于 CMU 本校学生的课程体验。 亮点在于这门课程实现了一个关系型数据库的Demo–bustub，并对组成部分进行修改，最后达到完成整个数据库的目的，非常的有意思。 近年来由于CMU15-445这门课的热度大增，无论是找工作还是保研的简历上都少不了这个课程。到了可以说是人手一个的地步（还有MIT6.824），但是最后的排行榜上真正完成4个项目并且有成绩的不过100余人。在这种背景下也催生出了很多卖课的机构和个人。还有种种乱象。暂且按下不表，进入主题。 前言 先附上 课程链接我原本是想要完成最新的课程即2023fall的，但是2023fall的P0直接就把我劝退了，相较于2022fall的P0我认为难度上升了不止一点。但是其他的Project的实现差别并不是太大，所以我选择了较为容易下手的2022fall的课程进行学习。 Project0-C++ Primer 还是先放上项目Project#0-C++primer链接 概述 这是一个相当于先导课程的项目，旨在培养和检验学生的现代C++编程能力 ，BusTub大量使用C++17，当你上手之后可能就会发现和你印象中的C++不一样。 在CMU如果你没能满分通过P0，那么你会被要求退课。 所需前置知识 我认为需要的前置知识主要包括C++11的新特性 这是在2023fall课程的一个可能是助教写的一个小demo包含了几个例子能够帮助你快速的上手c++11的新特性。 熟悉字典树能够理解字典树原理能够完成一个字典树的小demoLeetCode.208实现前缀字典树 可以先把这个做了，了解一下什么是字典树。 上图就是一个字典树的简单示意图 文件结构 在文件中作为字典树的架子文件中包含了三个类。 TrieNode TrieNodeWithValue Trie Task#1 字典树 先完成一个单线程版本的字典树，后期再考虑并发。 TrieNode TrieNode定义了一个Trie树的一个节点。 一个包含关键字的char类型`key_char_。 一个bool类型is_node的标志来标记这个节点是否是值节点 包含一个存储类型为 char to unique_ptr<TrieNode>映射的哈希表 需要注意的点： C++中智能指针std::unique_ptr的特性所带来的： The InsertChildNode and GetChildNode both return a pointer to unique_ptr 这个独享类型的智能指针也不支持被复制，所以要么使用std::move()把所有权交出去，要么就用get()函数把裸指针交出去。 the move constructor TrieNode(TrieNode &&other_trie_node) is used to transfer old TrieNode’s unique pointers to a new TrieNode。因为是unique_ptr所以在传递的时候不能对指针进行复制。（解决方法就是使用move()函数）。 ...

麻雀虽小五脏俱全的一个小而全的类unix教学用操作系统，由MIT开发 多核的操作系统，大约6000行还有大约300行的汇编，代码简洁易懂，有很多设计都值得借鉴。 一些特性 有进程管理功能 有虚拟地址和空间，pagetable 文件系统 时间片 21个syscall 用户程序 sh cat echo grep kill 能够被视为一个真正的操作系统 缺失的功能 用户ID 登录功能 文件保护 虚拟内存 无法联网 只有两个设备驱动 xv6特性 SMP 多线程共享内存 设备 UART 发送字节流，从一端到另一端 disk 磁盘驱动器 定时器 PLIC 平台级中断控制器，哪个核心应该被告诉中断 CLINT 本地中断控制器 内存管理 pagesize 4096B 一个freelist 没有可变的内存分配 没有“malloc” 三级页表 sv39，在pgtbl 巨页中有用到 调度器 基本的循环调度 时间片的大小是固定的 所有的核心共享一个就绪队列，循环的寻找可以执行的进程 不是完全的循环，如果在时间片内结束，会把这个进程放进队列然后换一个来 启动顺序 加载核心代码到固定的地址0x8000_0000,没有bios，bootloader bootblock 锁 自旋锁，sleep（），wakeup（） param.h 用户地址空间 函数的参数将会被放在栈中。 xv6的虚拟地址 sv39，三级页表之地 实际上xv6只使用了38位所以最大的是256GB xv6启动过程和组织 控制权逐步的转移 数据的类型 自旋锁 循环不断的检查，直到能够获取锁为止 test and set，原子的操作。 释放的时候直接修改值就行，可能看起来不是很原子，但是在内存里这被视为一个单独的操作。 ...