• Lumos-az/MiniSQL阅读笔记

    文章目录


    项目源码： MiniSQL: ZJU DBS Course Project – MiniSQL (gitee.com)
    2GpwVI.png

    处理SQL

    Interpreter::Interpret()负责映射不同关键字到不同处理方法， Interpreter::extractWord()负责一个个地获取SQL语句中的字符串

    int Interpreter::Interpret(const string &text) {
    int position = 0;
    int *shift = &position;
    string word = extractWord(text, shift);
    if (word == "create") {
        return execCreate(text, shift);
    } else if (word == "drop") {
        return execDrop(text, shift);
    } else if (word == "select") {
        return execSelect(text, shift);
    } else if (word == "insert") {
        return execInsert(text, shift);
    } else if (word == "delete") {
        return execDelete(text, shift);
    } else if (word == "quit") {
        return execQuit(text, shift);
    } else if (word == "execfile") {
        return execFile(text, shift);
    } else if (word == "show") {
        return execShow(text, shift);
    } else {
        cout << "Syntax error" << endl;
        return 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    创建

    Interpreter::execCreate()读取下一个词，将SQL映射到创建表或索引的方法上

    int Interpreter::execCreate(const string &text, int *shift) {
    string word = extractWord(text, shift);
    if (word == "table") {
        return execCreateTable(text, shift);
    } else if (word == "index") {
        return execCreateIndex(text, shift);
    } else {
        cout << "Syntax error for create" << endl;
        return 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    创建表

    Interpreter::execCreateTable()继续读取SQL，提取其中的表信息（表名、列名、列类型、约束），Attribute类将列名、列类型、约束flag封装，vector attributes就是列列表。将表名和列列表传入API::createTable()中创建表文件和表信息

    void API::createTable(const string& tableName, vector<Attribute> *attributes) {
    // Create table file by RecordManager
    rm->Createtable(tableName);
    // Create TableInfo
    if (cm.createTable(tableName, attributes) != -1)
        cout << "Success to create the table: " << tableName << "!" << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    RecordManager部分

    RecordManager负责管理表文件"…/data/XXX.txt"，实质还是调用BufferManager中的方法

    bool RecordManager::Createtable(string tablename) {
    string tablefilename = "../data/" + tablename + ".txt";

    if (bufferManager.LoadFile(tablefilename) > 0) {
        bufferManager.SaveFile(tablefilename);
        return true;
    }
    else
        return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    文件若存在BufferManager::LoadFile()会将文件read一个块到BufferManager::bufferPool的第0个块缓冲中，并且返回该文件有多少个块

    int BufferManager::LoadFile(const string& fileName){
    int size = -1, bufferIdx;
    ifstream is;
    is.open(fileName, ios::in);

    if(is.is_open()){
       //计算文件中的块数
        is.seekg(0, ios_base::end);//移动读写位置到开头
        size = ((int)is.tellg()/*读指针的位置*/ + BLOCK_SIZE - 1) / BLOCK_SIZE;
        //占用bufferPool中的第一个文件块，获取bufferIdx
        bufferIdx = FetchBlockFromDisk(is, 0);

        is.close();
        if(bufferIdx != -1){
            //update state
            bufferPool[bufferIdx]->fileName = fileName;
            fileBuffer[fileName][0] = bufferIdx;
            fileSize[fileName] = size;

            //return how many blocks in the file
            return size;
        }
        else{
            //Bufferpool is full.
            cout<<"[WARN]: Load fail. Bufferpool is full. Unpin some buffer."<<endl;
            return -1;
        }
        
    }
    else{
        //No such file, create one.
        //cout<<"[WARN]: No such file.\""<
        bool ret = CreateFile(fileName);
        if(ret){
            return 1;
        }
        else{
            return -1;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    //在硬盘文件中读取第idx个块到bufferPool中
int BufferManager::FetchBlockFromDisk(ifstream &is, int idx){
    int bufferIdx;
    is.seekg(idx*BLOCK_SIZE, is.beg);
        
    bufferIdx = GetFreeBufferIdx();
    if(bufferIdx != -1){
        is.read((char*)(bufferPool[bufferIdx]->block), BLOCK_SIZE);
        bufferPool[bufferIdx]->used = true;
        bufferPool[bufferIdx]->created = false;
        bufferPool[bufferIdx]->idx = idx;
        bufferPool[bufferIdx]->lastUsedTime = clock();//当前时间，用于LRU()返回最近最少使用时间
    }
    
    return bufferIdx;  
}

//取一个没有使用的bufferPool的索引，将文件信息赋到bufferPool上，fileBuffer（map>）对应文件的第0个块也指定为该bufferPool索引
bool BufferManager::CreateFile(const string& fileName){
    int bufferIdx = GetFreeBufferIdx();
    if(bufferIdx != -1){
        bufferPool[bufferIdx]->used = true;
        bufferPool[bufferIdx]->dirty = true;
        bufferPool[bufferIdx]->created = true;   
        bufferPool[bufferIdx]->idx = 0;
        bufferPool[bufferIdx]->fileName = fileName;
        bufferPool[bufferIdx]->lastUsedTime = clock();

        fileBuffer[fileName][0] = bufferIdx;
        fileSize[fileName] = 1;//当前文件有几个块
        return true;
    }
    else{
        return false;
    }
}

int BufferManager::GetFreeBufferIdx(){
    int bufferIdx, ret;
    if(freeBufferList == NULL){
        bufferIdx = LRU();//取最近最少使用的块索引
        if(bufferIdx == -1){
            //No buffer can be released with LRU
            cout<<"[ERROR]: No buffer can bu released. Unpin some buffers."<<endl;
            return -1; 
        }
        if(bufferPool[bufferIdx]->dirty){//该块数据为脏，应将数据写入硬盘
            fstream os;
            os.open(bufferPool[bufferIdx]->fileName);
            //这里没必要区分文件是否存在，fstream.open()可以在文件不存在时自动创建，无需使用ofstream.open()
            /*if(os.is_open()){
                WriteBlockToDisk(os, bufferPool[bufferIdx]->idx, bufferPool[bufferIdx]->block->data);
                os.close();
            }
            else{
                //file doesn't exist
                ofstream of;
                of.open(bufferPool[bufferIdx]->fileName);
                WriteNewBlockToDisk(of, bufferPool[bufferIdx]->idx, bufferPool[bufferIdx]->block->data);
                of.close();
            }*/
            WriteBlockToDisk(os, bufferPool[bufferIdx]->idx, bufferPool[bufferIdx]->block->data);
            os.close();
            
        }
        FreeBlock(bufferIdx);//块中数据已写入硬盘，释放块
    }

    ret = freeBufferList->bufferIdx;
    freeBufferList = freeBufferList->next;

    return ret;
}

void BufferManager::WriteBlockToDisk(fstream &os, int idx, const char* blockData){
    os.seekp(idx*BLOCK_SIZE, os.beg);
    os.write(blockData, BLOCK_SIZE);
}

int BufferManager::LRU(){
    int ret = -1;
    clock_t lruTime = clock(); 

    for(int i = 0; i < BUFFER_SIZE; i++){
        if(bufferPool[i]->used && !bufferPool[i]->pinned){
            if(bufferPool[i]->lastUsedTime <= lruTime){
                ret = i;
                lruTime = bufferPool[i]->lastUsedTime;
            }
        }
    }
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    总的来说，一个文件可以由多个块组成，块数据（4byte大小+4092byte数据）被封装到Block类中，Block又和最近使用时间、数据脏标记、使用标记、所在文件名等信息一起封装到Buffer类，BufferManager的核心是一个Buffer指针列表Buffer** bufferPool

    map> fileBuffer是文件名到块索引的映射

    FreeBuffer* freeBufferList是空闲块的索引的链表

    //将bufferPool中文件的所有脏块写入磁盘，并提交AppendFile或DeleteFileLastBlock。释放所有块，无论块是否固定。
void BufferManager::SaveFile(const string& fileName){
    
    ofstream of;
    fstream os;
    int idx, bufferIdx, size;
    vector<int> idxVec;
    
    os.open(fileName);
    if(os.is_open()){
        //the file exists
        //check if some block of the file is deleted
        os.seekp(0, ios_base::end);

        size = ((int)os.tellp() + BLOCK_SIZE - 1) / BLOCK_SIZE;
        
        os.close();
        //truncate the file
        if(size > fileSize[fileName]){
            //truncate(fileName.c_str(), fileSize[fileName]*BLOCK_SIZE);
        }
        os.open(fileName);
        if(fileBuffer.find(fileName) != fileBuffer.end()){
            
            //获取文件名对应的块索引列表
            for (auto iter = fileBuffer[fileName].begin(); iter != fileBuffer[fileName].end(); ++iter){
                idxVec.push_back(iter->first);
            }
            //将脏的块写入硬盘文件
            for (auto iter = idxVec.begin(); iter != idxVec.end(); ++iter) {
                idx = *iter;
                bufferIdx = fileBuffer[fileName][idx];   
                if(bufferPool[bufferIdx]->dirty){
                    WriteBlockToDisk(os, idx, bufferPool[bufferIdx]->block->data);
                }
                bufferPool[bufferIdx]->dirty = false;
                //FreeBlock(bufferIdx);
            }
        }

        os.close();
    }
    else{
        //the file does not exist
        of.open(fileName);
            for (auto iter = fileBuffer[fileName].begin(); iter != fileBuffer[fileName].end(); ++iter){
                idxVec.push_back(iter->first);
            }
            for (auto iter = idxVec.begin(); iter != idxVec.end(); ++iter) {
                idx = *iter;
                bufferIdx = fileBuffer[fileName][idx];   
                if(bufferPool[bufferIdx]->dirty){
                    WriteNewBlockToDisk(of, idx, bufferPool[bufferIdx]->block->data);
                }
                bufferPool[bufferIdx]->dirty = false;
                //FreeBlock(bufferIdx);
            }
        of.close();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    CatalogManager部分

    该部分注重表列信息的处理，是对RecordManager构建的表和块的框架（如果是初始创建表就只是创建的表文件）的"内容"的补充，就是将表列信息保存到内存的bufferPool中，当然是保存到TableInfo.txt文件对应的块中，直到BufferManager对象销毁时调用析构函数才保存到硬盘。

    int CatalogManager::createTable(const string& tableName, vector<Attribute> *attributes) {
    // If the table exists
    if (findTable(tableName)) {
        cout << "Table already exists!" << endl;
        return -1;
    }
    
    // Get table info
    string tableInfo = createTableInfo(tableName, attributes);

    int tableInfoLength = (int) tableInfo.length();

    // 遍历块以查找是否有存储tableInfo的空间
    int fileSize = bufferManager.GetFileSize(TABLE_INFO_PATH);//表信息文件TableInfo.txt
    for (int i = 0; i < fileSize; ++i) {
        Block *block = bufferManager.GetFileBlock(TABLE_INFO_PATH, i);
        string content(block->data);
        int contentLength = (int) content.length();
        // If there is enough space for table info
        if (contentLength + tableInfoLength <= BLOCK_SIZE) {
            content.append(tableInfo);
//            cout << content << endl;
            strcpy(block->data, content.c_str());
            block->SetDirty(true);

            return 1;
        }
    }

    // No space, so need to append a block
    bufferManager.AppendFile(TABLE_INFO_PATH);
    Block *block = bufferManager.GetFileBlock(TABLE_INFO_PATH, fileSize++);
    block->SetPin(true);
    strcpy(block->data, tableInfo.c_str());

    return 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    int CatalogManager::findTable(const string& tableName) {
    int fileSize = bufferManager.GetFileSize(TABLE_INFO_PATH);//获取表信息文件TableInfo.txt有多少个块
    for (int i = 0; i < fileSize; ++i) {//遍历文件的所有块
        Block *block = bufferManager.GetFileBlock(TABLE_INFO_PATH, i);
        string content(block->data);
        int find = (int) content.find("TABLE_NAME:" + tableName);//查找块数据中有无"TABLE_NAME:..."字符串
        if (find != std::string::npos)
            return 1;
    }

    return 0;
}

int BufferManager::GetFileSize(const string& fileName){
    if(fileBuffer.find(fileName) != fileBuffer.end()){
        //file is registered
        return fileSize[fileName];
    }
    else{
        return -1;
    }
}   

Block* BufferManager::GetFileBlock(const string& fileName, int idx){
    int bufferIdx;
    ifstream is;
    if(fileBuffer.find(fileName) != fileBuffer.end() && idx >= 0 && idx < fileSize[fileName]){
        //文件已注册，idx是合理的
        if(fileBuffer[fileName].find(idx) != fileBuffer[fileName].end()){
            //block already in the bufferPool
            bufferIdx = fileBuffer[fileName][idx];
        }
        else{
            //block not in the bufferPool, fetch block from disk
            is.open(fileName, ios::in);
            bufferIdx = FetchBlockFromDisk(is, idx);
            is.close();

            //update state
            bufferPool[bufferIdx]->fileName = fileName;
            fileBuffer[fileName][idx] = bufferIdx;
        }
        bufferPool[bufferIdx]->lastUsedTime = clock();

        return bufferPool[bufferIdx]->block;
    }
    else{
        //illeagl condition
        return NULL;
    }
}

/* tableInfo: TABLE_NAME:tableName|ATTRIBUTE_NUM:attributeNum｜PRIMARY_KEY:primaryKey|INDEX_NUM:indexNum|ATTRIBUTE_INFO_0:attributeName,dataType,charSize,primaryKey,unique,index|# */
//其实就是根据传入的表名和列列表拼出表信息字符串
string CatalogManager::createTableInfo(const string &tableName, vector<Attribute> *attributes) {
    string tableInfo;

    // Store the name of the table
    tableInfo.append("TABLE_NAME:" + tableName + "|");

    // Store the number of attributes
    tableInfo.append("ATTRIBUTE_NUM:" + to_string(((*attributes).size())) + "|");

    // Store the primary key
    bool hasKey = false;
    for (const auto& attribute : (*attributes))
        if (attribute.primaryKey) {
            hasKey = true;
            tableInfo.append("PRIMARY_KEY:" + attribute.name + "|");
            break;
        }
    if (!hasKey)
        tableInfo.append("PRIMARY_KEY:NONE|");


    // Store the number of indexes
    int indexNum = 0;
    for (const auto& attribute : (*attributes)) {
        if (attribute.index != "none")
            indexNum++;
    }
    tableInfo.append("INDEX_NUM:" + to_string(indexNum) + "|");

    // Store the information of attributes
    int attributeCount = 0;
    for (const auto& attribute : (*attributes)) {
        tableInfo.append("ATTRIBUTE_INFO_" + to_string(attributeCount) + ":");
        tableInfo.append(attribute.name + "," + to_string(attribute.dataType) + "," +
                         to_string(attribute.charSize) + "," + to_string(attribute.primaryKey) + "," +
                         to_string(attribute.unique) + "," + attribute.index + "|");
        attributeCount++;
    }

    // End with "#"
    tableInfo.append("#");

    return tableInfo;
}

void BufferManager::AppendFile(const string& fileName){
    int bufferIdx = GetFreeBufferIdx();

    bufferPool[bufferIdx]->used = true;
    bufferPool[bufferIdx]->dirty = true;
    bufferPool[bufferIdx]->created = true;   
    bufferPool[bufferIdx]->idx = fileSize[fileName];
    bufferPool[bufferIdx]->fileName = fileName;
    bufferPool[bufferIdx]->lastUsedTime = clock();

    fileBuffer[fileName][fileSize[fileName]] = bufferIdx;
    fileSize[fileName] = fileSize[fileName] + 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112

    创建索引

    与Interpreter::execCreateTable()类似，Interpreter::execCreateIndex()继续读取输入SQL的词，获取到索引名、所在表表名、索引的目标列列名（只支持单列索引），进入API层

    索引结构（B+树的属性成员）虽然通过这个方法保存到索引文件上，但是索引数据（B+树的结点数据）没有写入硬盘，而是呆在内存的bufferPool中。当然表信息肯定要更新到内存中的bufferPool内TableInfo.txt对应的块中。索引数据和表信息直到BufferManager析构时才保存到硬盘（实际上不止二者，所有的bufferPool中的块都在这时保存到硬盘）

    void API::createIndex(const string &tableName, const string &attributeName, const string &indexName) {
    // Create index by IndexManager
    vector<Attribute> attributes = getTableAttribute(tableName);
    for (auto attribute : attributes) {
        if (attribute.name == attributeName) {
            im.createIndex(tableName, attribute);
            createNewIndex(tableName, attributeName, indexName);
        }
    }

    // Update the tableInfo
    cm.createIndex(tableName, attributeName, indexName);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    IndexManager::createIndex部分

    这一部分目的是把索引文件给创建出来，并把B+树的基础信息写进文件

    //在IndexManager层对三种数据类型分情况创建B+树
//这里创建对象没有使用new，BplusTree对象创建在栈上，作用域结束时销毁，因此在构造函数结尾有调用写入硬盘方法
bool IndexManager::createIndex(string _tableName, Attribute _attribute)
{
	string indexFileName = _tableName + "_" + _attribute.name + ".index";
	bufferManager.CreateFile(indexFileName);

	switch (_attribute.dataType) {
	case 0: {
		BplusTree<int> bptree = BplusTree<int>(_tableName, _attribute.name, getKeyLength(_attribute));
	}
		break;
	case 1: {
		BplusTree<float> bptree = BplusTree<float>(_tableName, _attribute.name, getKeyLength(_attribute));
	}
		break;
	case 2: {
		BplusTree<string> bptree = BplusTree<string>(_tableName, _attribute.name, getKeyLength(_attribute));
	}
		break;
	default:
		cout << "wrong attribute type" << endl;
		return false;
		break;
	}
	return true;
}

//新建B+树
template<typename keyType>
BplusTree<keyType>::BplusTree(string _tableName, string _attributeName, uint32_t _keyLength)
{
	this->indexFileName = _tableName + "_" + _attributeName + ".index";//索引文件名
	this->keyLength = _keyLength;
	this->nodeCount = 1;
	this->root = 1;
	this->freePageCount = 0;

	bufferManager.AppendFile(indexFileName);
	BplusTreeNode<keyType>* node = new BplusTreeNode<keyType>(/*isLeafNode*/true, /*keyLength*/keyLength, /*parent*/0, /*parent*/1);
	Block* rootBlock = bufferManager.GetFileBlock(indexFileName, 1);
	node->setLastPointer(0);//尾插pageVector
	node->writeToDisk(rootBlock);

	writeToDisk();
}

//将树保存到硬盘的索引文件内
template<typename keyType>
void BplusTree<keyType>::writeToDisk()
{
	Block* _block = bufferManager.GetFileBlock(indexFileName, 0);
	_block->SetPin(true);
	_block->SetDirty(true);

    //将B+树属性成员存入索引文件块中
	memcpy(_block->data + KEY_LENGTH_OFFSET, &keyLength, KEY_LENGTH_SIZE);
	memcpy(_block->data + NODE_COUNT_OFFSET, &nodeCount, NODE_COUNT_SIZE);
	memcpy(_block->data + ROOT_POINTER_OFFSET, &root, ROOT_POINTER_SIZE);
	memcpy(_block->data + FREE_PAGE_COUNT_OFFSET, &freePageCount, FREE_PAGE_COUNT_SIZE);

	int pageOffset = TREE_HEADER_SIZE;
	int step = sizeof(uint32_t);
	for (uint32_t i = 0; i < freePageCount; i++) {
		memcpy(_block->data + pageOffset, &freePages[i], sizeof(uint32_t));
		pageOffset += step;
	}

	_block->SetPin(false);
	bufferManager.SaveFile(indexFileName);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    API::createNewIndex部分

    这一部分根据传入的索引列进行B+树的构建，具体就是取出表文件中索引列的数据，将每个记录的该列数据定为一个key，value是一个能确定当前记录的RecordPosition结构体（指定块索引和块内记录编号），这样当where指定索引列的值时就可以快速定位到记录的位置（虽然一开始key和value参数名相反，之后会调换的）。然后value存到BplusTreeNode::recordVector，key存到BplusTreeNode::keyVector，两者会交叉着（先recordVector[i]再keyVector[i]）被存到索引文件对应的块中

    void API::createNewIndex(const string& tableName, const string& attributeName, const string& indexName) {

    vector<Attribute> Attributes;
    Attributes = getTableAttribute(tableName);//表列列表

    struct RecordPosition recordposition;

    int p = 1;//属性起始位置
    int attributeaddress;
    for (int h = 0; h < Attributes.size(); h++) {
        if (Attributes[h].name == attributeName) {
            attributeaddress = h;//传入列的索引
            break;

        }
        p += Attributes[h].charSize;
    }

    int recordsize = rm->getrecordsize(&Attributes);

    string value;
    string tablefilename = "../data/" + tableName + ".txt";

    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }

    int buffernum = bufferManager.GetFileSize(tablefilename);

    for (int i = 0; i < buffernum; i++) {

        Block *btmp = bufferManager.GetFileBlock(tablefilename, i);//遍历文件的块列表
        int recordNum = (btmp->GetSize() - 4) / recordsize;//这个块里有多少条记录

        for (int j = 0; j < recordNum; j++) {
            value = (*(btmp->GetRecords(j, j + 1, recordsize)))[0];//返回1条（[j+1]-[j]）记录

            if (value.at(0) == '%') {//一条记录的开头规定为%
                value = value.substr(p, Attributes[attributeaddress].charSize);//取出传入列在该记录中的数据
                recordposition.blockNum = i + 1;
                recordposition.recordNum = j + 1;


                if (Attributes[attributeaddress].dataType == 0) {
                    int n = stoi(value);//数据类型转换
                    string value1 = to_string(n);
                    insertIndex(tableName, Attributes[attributeaddress], value1, recordposition);

                } else if (Attributes[attributeaddress].dataType == 1) {
                    float f = stof(value);
                    string value1 = to_string(f);
                    insertIndex(tableName, Attributes[attributeaddress], value1, recordposition);
                } else {
                    int k;
                    for (k = 0; k < Attributes[attributeaddress].charSize; k++) {
                        if (value.at(k) != '!') break;
                    }
                    value = value.substr(k);
                    insertIndex(tableName, Attributes[attributeaddress], value, recordposition);
                }
            }
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    void API::insertIndex(const string& tableName, Attribute _attribute, const string& _value, struct RecordPosition recordposition)
{
    char* value;
    int tempInt = atoi(_value.c_str());
    float tempFloat = atof(_value.c_str());

    //数据转换成不同类型的字符串
    switch (_attribute.dataType) {
        //int
        case 0: value = (char*)&tempInt; break;
            //float
        case 1: value = (char*)&tempFloat; break;
            //string
        default: value = (char*)&_value; break;
    }
    im.insertIndex(tableName, _attribute, value, recordposition);
}


bool IndexManager::insertIndex(string _tableName, Attribute _attribute, char* _key, RecordPosition _value)
{
    switch (_attribute.dataType) {
        case 0: {
            BplusTree<int> bptree = BplusTree<int>(_tableName, _attribute.name);
            bptree.insertValueWithKey(CHAR2INT(_key), _value); 
        }
            break;
        case 1:{
            BplusTree<float> bptree = BplusTree<float>(_tableName, _attribute.name);
            bptree.insertValueWithKey(CHAR2FLOAT(_key), _value); 
        }
            break;
        case 2: {
            BplusTree<string> bptree = BplusTree<string>(_tableName, _attribute.name);
            bptree.insertValueWithKey(CHAR2STRING(_key), _value);
        }
            break;
        default:
            cout << "wrong attribute type" << endl;
            return false;
            break;
    }
    return true;
}

//两个参数的B+树构造函数，完成了从索引文件块取值构建B+树的工作
template<typename keyType>
BplusTree<keyType>::BplusTree(string _tableName, string _attributeName)
{
	this->indexFileName = _tableName + "_" + _attributeName + ".index";
	Block* _block = bufferManager.GetFileBlock(indexFileName, 0);

	_block->SetPin(true);

    //将索引文件块中数据取出放进B+树属性成员
	memcpy(&keyLength, _block->data + KEY_LENGTH_OFFSET, KEY_LENGTH_SIZE);
	memcpy(&nodeCount, _block->data + NODE_COUNT_OFFSET, NODE_COUNT_SIZE);
	memcpy(&root, _block->data + ROOT_POINTER_OFFSET, ROOT_POINTER_SIZE);
	memcpy(&freePageCount, _block->data + FREE_PAGE_COUNT_OFFSET, FREE_PAGE_COUNT_SIZE);

	int pageOffset = TREE_HEADER_SIZE;
	int step = sizeof(uint32_t);
	for (uint32_t i = 0; i < freePageCount; i++) {
		uint32_t _freePage;
		memcpy(&_freePage, _block->data + pageOffset, sizeof(uint32_t));

		freePages.push_back(_freePage);
		pageOffset += step;
	}

	_block->SetPin(false);
}

template<typename keyType>
bool BplusTree<keyType>::insertValueWithKey(const keyType& key, RecordPosition value)
{
	BplusTreeNode<keyType>* node = getNode(root);//获取root结点
	uint32_t nodeNumber = root;

	while (node != nullptr && !node->isLeaf()) {//单个根节点是叶子节点
		nodeNumber = node->findChildWithKey(key);//在内部节点中查找带有key的子页
		delete node;
		node = getNode(nodeNumber);
	}

	if (node == nullptr) {
		cout << "The node is null" << endl;
		return false;
	}

	if (node->insertValueWithKey(key, value)) {

		if (node->isOverLoad()) {
            //如果结点过载了就分割结点
			node->splitNode(this);
		}
		else {
			writeNodeToDisk(node, nodeNumber);
		}

		delete node;
	}
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    template<typename keyType>
bool BplusTreeNode<keyType>::insertValueWithKey(const keyType& _key, RecordPosition _value)
{
	// If the node is not a leaf node
	if (!isLeaf()) {
		cout << "Try to insert value in a internal node" << endl;
		return false;
	}
	//insert data into a leaf node
	int sub = lower_bound(keyVector.begin(), keyVector.end(), _key) - keyVector.begin();//lower_bound()查找不小于目标值的第一个元素
	keyVector.insert(keyVector.begin() + sub, _key);//参数1之前插入
	recordVector.insert(recordVector.begin() + sub, _value);

	dataCount++;
	return true;
}

template<typename keyType>
void BplusTree<keyType>::writeNodeToDisk(BplusTreeNode<keyType>* node, uint32_t pageNumber)
{
	Block* nodeBlock = bufferManager.GetFileBlock(indexFileName, pageNumber);
	node->writeToDisk(nodeBlock);
}

template<typename keyType>
void BplusTreeNode<keyType>::writeToDisk(Block* _block)
{
	_block->SetPin(true);
	_block->SetDirty(true);

	memcpy(_block->data + IS_LEAF_OFFSET, &isLeafNode, IS_LEAF_SIZE);
	memcpy(_block->data + KEY_LENGTH_OFFSET, &keyLength, KEY_LENGTH_SIZE);
	memcpy(_block->data + DATA_COUNT_OFFSET, &dataCount, DATA_COUNT_SIZE);
	memcpy(_block->data + PARENT_POINTER_OFFSET, &parent, PARENT_POINTER_SIZE);

	int valueOffset = NODE_HEADER_SIZE;
	int valueSize = isLeaf() ? sizeof(RecordPosition) : sizeof(uint32_t);
	int keyOffset = valueOffset + valueSize;
	int step = valueSize + keyLength;

	if (isLeaf()) {
		for (uint32_t i = 0; i < getDataCount(); i++) {
			memcpy(_block->data + valueOffset, &recordVector[i], valueSize);

			if (instanceof<string>(&keyVector[i])) {
				string temp = *(string*)&keyVector[i];
				memcpy(_block->data + keyOffset, temp.c_str(), keyLength);
			}
			else {
				memcpy(_block->data + keyOffset, &keyVector[i], keyLength);
			}

			valueOffset += step;
			keyOffset += step;
		}
	}
	else {
		for (uint32_t i = 0; i < getDataCount(); i++) {
			memcpy(_block->data + valueOffset, &pageVector[i], valueSize);

			if (instanceof<string>(&keyVector[i])) {
				string temp = *(string*)&keyVector[i];
				memcpy(_block->data + keyOffset, temp.c_str(), keyLength);
			}
			else {
				memcpy(_block->data + keyOffset, &keyVector[i], keyLength);
			}

			valueOffset += step;
			keyOffset += step;
		}
	}

	if (!pageVector.empty())
		memcpy(_block->data + valueOffset, &pageVector.back(), sizeof(uint32_t));

	_block->SetPin(false);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    CatalogManager::createIndex部分

    将表中列的索引名更新，删除表信息后重新创建表信息

    int CatalogManager::createIndex(const string &tableName, const string &attributeName, const string &indexName) {
    // If the table not exist
    if (!findTable(tableName)) {
        cout << "Table not exists!" << endl;
        return 0;
    }

    // If the attribute not exist
    if(!findAttribute(tableName, attributeName)) {
        cout << "Attribute not exists!" << endl;
        return 0;
    }

    // Create the index
    vector<Attribute> attributes = getAttribute(tableName);
    for (int i = 0; i < attributes.size(); i++) {
        if (attributes[i].name == attributeName) {
            attributes[i].index = indexName;
        }
    }

    // Update the tableInfo
    dropTable(tableName);
    createTable(tableName, &attributes);

    cout << "Success to creat index " << indexName << " on " << tableName << endl;
    return 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    插入

    int Interpreter::execInsert(const string &text, int *shift) {
    string tableName;
    vector<string> tuple;
    vector<vector<string>> tuples;

    //检查语法错误
    // Determine whether "into" exists
    string word = extractWord(text, shift);
    if (word != "into") {
        cout << "Syntax error for no \"into\"" << endl;
        return 0;
    }

    word = extractWord(text, shift);
    tableName = word;

    // Determine whether "values" exists
    word = extractWord(text, shift);
    if (word != "values") {
        cout << "Syntax error for no \"values\"" << endl;
        return 0;
    }

    // Determine whether "(" exists
    word = extractWord(text, shift);
    if (word != "(") {
        cout << "Syntax error for no \"(\"" << endl;
        return 0;
    }

    // 处理插入值
    word = extractWord(text, shift);
    do {
        tuple.push_back(word);
        word = extractWord(text, shift);
        if (word == ",")
            word = extractWord(text, shift);

        // Determine whether ")" exists
        if (word == ";") {
            cout << "Syntax error for no \")\"" << endl;
            return 0;
        }
    } while (word != ")");
    tuples.push_back(tuple);

    api->insertValue(tableName, &tuple);
    return 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    void API::insertValue(const string& tableName, vector<string>* tuples)
{
    int step;
    int attrindex[10];
    int p = 0;

    vector<Attribute> Attributes;
    Attributes = getTableAttribute(tableName);//表的列列表

    for (int j = 0; j < Attributes.size(); j++)
    {
        step = Attributes[j].charSize;
        if (Attributes[j].index != "none") {
            attrindex[p] = j;//有索引的列在Attributes中的下标数组
            p++;
        }
    }

    vector<string> str;
    for (int i = 0; i < (*tuples).size(); i++) {
        step = Attributes[i].charSize;//每个列的数据长度
        string temp((*tuples)[i]);
        int interval = step - temp.length();//列的数据长度和插入的值长度的差（空闲的长度）
        if (Attributes[i].dataType == Attribute::TYPE_CHAR) {
            for (int j = 0; j < interval; ++j) {
                temp = "!" + temp;//补上空闲的长度
            }
        }
        else {
            for (int j = 0; j < interval; ++j) {
                temp = "0" + temp;
            }
        }
        str.push_back(temp);//补全长度的待插入数组
    }

    string record = "%";


    for (int j = 0;j < str.size();j++)
        record.append(str[j]);//待插入数组按顺序拼成一个字符串，开头加一个%

    int recordsize = record.size();

    struct RecordPosition recordposition;

    recordposition = rm->InsertRecord(tableName, &record, recordsize);
    for (int k = 0;k < p;k++) {
        insertIndex(tableName, Attributes[attrindex[k]], (*tuples)[attrindex[k]], recordposition);//插入值时若列本就有索引，就让插入的值也具备索引
    }

    cout << "Success to insert value!" << endl;
}

//将记录插入到表文件的块中
struct RecordPosition RecordManager::InsertRecord(string tablename, string* record, int recordsize) {

    string tablefilename = "../data/" + tablename + ".txt";

    struct RecordPosition recordposition;
    recordposition.blockNum = 0;
    recordposition.recordNum = 0;//初始化
    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }

    int i = bufferManager.GetFileSize(tablefilename);
    class Block* btmp = bufferManager.GetFileBlock(tablefilename, i - 1);
    int recordNum = (btmp->GetSize() - 4) / recordsize;

    if (btmp == NULL) {
        cout << "insert " << tablename << " record fails" << endl;
        return recordposition;
    }

    if (recordsize + 1 <= BLOCK_SIZE - btmp->GetSize()) {
        //当前块可以容纳要插入的记录
        char* addr = btmp->data + btmp->GetSize();//当前块剩余空间的起始地址

        memcpy(addr, record->c_str(), recordsize);//复制记录到块
        btmp->SetSize(btmp->GetSize() + recordsize);
        btmp->SetDirty(true);

        recordposition.blockNum = i;
        recordposition.recordNum = recordNum + 1;
        return recordposition;
    }
    else {
        bufferManager.SaveFile(tablefilename);
        bufferManager.AppendFile(tablefilename);
        return InsertRecord(tablename, record, recordsize);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    删除

    int Interpreter::execDelete(const string &text, int *shift) {
    string tableName;

    // Determine whether "from" exists
    string word = extractWord(text, shift);
    if (word != "from") {
        cout << "Syntax error for no \"from\"" << endl;
        return 0;
    }

    word = extractWord(text, shift);
    tableName = word;

    //判断句子是否结束
    word = extractWord(text, shift);
    // Sentence is over
    if (word == ";") {
        api->deleteTable(tableName);
        return 1;
    }
    // 存在条件语句
    else if (word == "where") {
        vector<Condition> conditions;
        string attributeName;
        int operate;
        string value;

        // 提取所有条件
        do {
            word = extractWord(text, shift);
            attributeName = word;//条件左值
            word = extractWord(text, shift);
            if (word == "=")
                operate = Condition::OPERATOR_EQUAL;
            else if (word == "<")
                operate = Condition::OPERATOR_LESS;
            else if (word == ">")
                operate = Condition::OPERATOR_MORE;
            else if (word == "<=")
                operate = Condition::OPERATOR_LESS_EQUAL;
            else if (word == ">=")
                operate = Condition::OPERATOR_MORE_EQUAL;
            else if (word == "<>")
                operate = Condition::OPERATOR_NOT_EQUAL;
            else {
                cout << "Syntax error for condition" << endl;
                return 0;
            }
            word = extractWord(text, shift);
            value = word;//条件右值

            // 创建并存储条件
            Condition condition(attributeName, operate, value);
            conditions.push_back(condition);

            word = extractWord(text, shift);
        } while (word == "and");

        // 确定";"是否存在
        if (word != ";") {
            cout << "Syntax error for no \";\"" << endl;
            return 0;
        }
        
        api->deleteRecord(tableName, &conditions);
        return 1;
    } else {
        cout << "Syntax error" << endl;
        return 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    删除表

    void API::deleteTable(const string &tableName) {

    vector<Attribute> Attributes;
    Attributes = getTableAttribute(tableName);
    rm->DeleteAllRecords(tableName, &Attributes);
    cout << "Success to delete the table!" << endl;
}

bool RecordManager::DeleteAllRecords(string tablename, vector<Attribute>* Attributes)
{
    string tablefilename = "../data/" + tablename + ".txt";
    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }
    bufferManager.ResetFile(tablefilename);
    
    return true;
}

void BufferManager::ResetFile(const string& fileName){
    vector<int> bufferIdxVec;
    int bufferIdx, firstBufferIdx;
    ifstream is;
    ofstream os;
    //Block* block;
    
    if(fileBuffer.find(fileName) != fileBuffer.end()){//查找表文件
        //block = GetFileBlock(fileName, 0);
        
        if(fileBuffer[fileName].find(0) == fileBuffer[fileName].end()){
            //该表文件没有块
            is.open(fileName);
            firstBufferIdx = FetchBlockFromDisk(is, 0);
            is.close();
            bufferPool[firstBufferIdx]->fileName = fileName;
            fileBuffer[fileName][0] = firstBufferIdx;
        }
        else{
            firstBufferIdx = fileBuffer[fileName][0];//文件在bufferPool中的块索引列表中的第一个索引
        }

        bufferPool[firstBufferIdx]->pinned = true;

        //Clear the block
        for (auto iter = fileBuffer[fileName].begin(); iter != fileBuffer[fileName].end(); ++iter){//遍历文件的块索引列表
            if(iter->first != 0){//剔除第一个块，因为第一个块存放信息
                bufferIdxVec.push_back(iter->second);//待删除的块索引
            }
        }
        for (auto iter = bufferIdxVec.begin(); iter != bufferIdxVec.end(); ++iter) {
            bufferIdx = *iter;
            FreeBlock(bufferIdx);
        }

        //Make the first block empty
        bufferPool[firstBufferIdx]->block->SetSize(4);

        os.open(fileName);//ofstream.open()清空文件写入
        os.seekp(0, os.beg);
        os.write(bufferPool[firstBufferIdx]->block->data, BLOCK_SIZE);
        os.close();

        
        fileSize[fileName] = 1;
        bufferPool[firstBufferIdx]->lastUsedTime = clock();
        bufferPool[firstBufferIdx]->dirty = false;
        bufferPool[firstBufferIdx]->pinned = false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    删除记录?

    void API::deleteRecord(const string &tableName, vector<Condition> *conditions) {
    vector<Attribute> Attributes;
    Attributes = getTableAttribute(tableName);
    deletewithconditions(tableName, &Attributes, conditions);
}

void API::deletewithconditions(string tablename, vector<Attribute>* Attributes, vector<Condition>* conditions)
{
    int n = conditions->size();
    int s = Attributes->size();
    int recordsize = rm->getrecordsize(Attributes);//表列大小之和（记录的大小）

    vector<RecordPosition> repo;

    int flag = 0;//标记是否找有索引
    int flag1 = 0;//标记是否有数据被删除


    vector<Condition> condwithouindex; //将没有index的conditions放在一起

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < s;j++) {
            if ((*conditions)[i].name == (*Attributes)[j].name)//遍历表列列表找条件左值
            {
                if ((*Attributes)[j].index != "none" && flag == 0) {

                    repo = indexforcondition(tablename, (*Attributes)[j], (*conditions)[i].operate, (*conditions)[i].value); //在API里调用index搜索，返回有Index的查找条件对应数据所在位置
                    flag = 1;
                }
                else {
                    //无索引或者前面的循环已找到了索引，但是因为该项目只支持单列索引，所以只有可能是无索引
                    condwithouindex.push_back((*conditions)[i]);
                }
            }
        }
    }
    if (flag == 1) {
        flag1 = rm->selectwithoutindex(tablename, Attributes, &repo, &condwithouindex); //获得没有条件、不在索引上的被筛选出数据的位置
    }
    else {
        flag1 = rm->deletebyorders(tablename, Attributes, conditions);
    }

    bufferManager.SaveFile(tablename);

    if (flag1 == 0) {
        cout << "There are no records can be deleted!" << endl;
    }
    else {
        cout << "Sucessfully deleted!" << endl;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    vector<RecordPosition> API::indexforcondition(const string& tableName, Attribute attribute, int operate, const string& _value)
{
    char* value;
    int tempInt = atoi(_value.c_str());
    float tempFloat = atof(_value.c_str());

    switch (attribute.dataType) {
        //int
        case 0: value = (char*)&tempInt; break;
            //float
        case 1: value = (char*)&tempFloat; break;
            //string
        default: value = (char*)&_value; break;
    }

    return im.findIndexBlockNumber(tableName, attribute, value, operate);
}

//通过索引文件查找块号
vector<RecordPosition> IndexManager::findIndexBlockNumber(string _tableName, Attribute _attribute, char* _key, int type)
{
	vector<RecordPosition> result;

	switch (_attribute.dataType) {
	case 0: {
		BplusTree<int> bptree = BplusTree<int>(_tableName, _attribute.name);
		bptree.findValueWithKey(CHAR2INT(_key),result,type);
	}
		break;
	case 1: {
		BplusTree<float> bptree = BplusTree<float>(_tableName, _attribute.name);
		bptree.findValueWithKey(CHAR2FLOAT(_key),result,type);
	}
		break;
	case 2: {
		BplusTree<string> bptree = BplusTree<string>(_tableName, _attribute.name);
		bptree.findValueWithKey(CHAR2STRING(_key),result,type);
	}
		break;
	default:
		cout << "wrong attribute type" << endl;
		break;
	}

	return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    //不使用索引进行SELECT
int RecordManager::selectwithoutindex(string tablename, vector<Attribute>* Attributes, vector<RecordPosition>* rep, vector<Condition>* conditions) {
    string tablefilename = "../data/" + tablename + ".txt";

    int recordsize = getrecordsize(Attributes);

    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }

    int flag = 0;

    Block* btmp;
    string str;
    for (int i = 0; i < rep->size(); i++) {
        btmp = bufferManager.GetFileBlock(tablefilename, (*rep)[i].blockNum - 1);
        str = (*(btmp->GetRecords((*rep)[i].recordNum - 1, (*rep)[i].recordNum, recordsize)))[0];

        if (str.at(0) == '%') {

            if (isSatisfied(Attributes, &str, conditions)) {
                if (flag == 0) printouttablehead(Attributes);//打印表头
                putout(str, Attributes);
                flag = 1;
            }
        }
    }
    return flag;
}

//记录字符串record的Attributes中标识的列是否满足条件conditions
bool RecordManager::isSatisfied(vector<Attribute>* Attributes, string* record, vector<Condition>* conditions)
{

    if(conditions->size() == 0)
        return true;

    int s = conditions->size();
    int n = Attributes->size();
    int attr[100];
    int position[100];
    int step = 0;


    for (int i = 0; i < s; i++)
    {
        position[i] = 0;

        for (int j = 0; j < n; j++)
        {
            step += (*Attributes)[j].charSize;

            if (((*Attributes)[j].name) == ((*conditions)[i].name))
            {

                attr[i] = j;

                position[i] += step;
                break;
            }

        }
        step = 0;
    }

    for (int k = 0;k < s;k++)
    {

        if ((*conditions)[k].value != "") {

            if ((*Attributes)[attr[k]].dataType == 0) {

                int step = (*Attributes)[attr[k]].charSize;
                string com = (*conditions)[k].value;
                string tem = (*record).substr(position[k] - step + 1, step);
                int temp = stoi(tem);
                int con = stoi(com);


                switch ((*conditions)[k].operate) {
                case 0: if (!(temp == con)) return false; break;
                case 1: if (!(temp != con)) return false; break;
                case 2: if (!(temp < con)) return false; break;
                case 3: if (!(temp > con)) return false; break;
                case 4: if (!(temp <= con)) return false; break;
                case 5: if (!(temp >= con)) return false; break;
                default: break;

                }
            }
            else if ((*Attributes)[attr[k]].dataType == 1) {

                int step = (*Attributes)[attr[k]].charSize;
                string com = (*conditions)[k].value;
                string tem = (*record).substr(position[k] - step + 1, step);
                float temp = stof(tem);
                float con = stof(com);


                switch ((*conditions)[k].operate) {
                case 0: if (!(abs(temp - con) < 1e-3)) return false; break;
                case 1: if (!(temp != con)) return false; break;
                case 2: if (!(temp < con)) return false; break;
                case 3: if (!(temp > con)) return false; break;
                case 4: if (!(temp <= con)) return false; break;
                case 5: if (!(temp >= con)) return false; break;
                default: break;

                }
            }
            else {

                int step = (*Attributes)[attr[k]].charSize;
                string con = (*conditions)[k].value;
                string temp = (*record).substr(position[k] - step + 1, step);

                int h;
                for (h = 0;h < step;h++) {
                    if (temp.at(h) != '!') break;
                }
                temp = temp.substr(h);

                switch ((*conditions)[k].operate) {
                case 0: if (!(temp == con)) return false; break;
                case 1: if (temp == con)   return false; break;
                case 2: if (!(temp < con)) return false; break;
                case 3: if (!(temp > con)) return false; break;
                case 4: if (!(temp < con || temp == con)) return false; break;
                case 5: if (!(temp > con || temp == con)) return false; break;
                default: break;
                }

            }
        }
    }
    return true;
}

void RecordManager::printouttablehead(vector<Attribute>* Attributes)
{

    cout << "|";
    for (int i = 0;i < Attributes->size();i++)
    {
        cout.setf(ios::left);
        cout.width(10);
        cout << (*Attributes)[i].name;
        cout << "|";

    }
    cout << endl;
}

void RecordManager::putout(string str, vector<Attribute>* Attributes)
{

    int p = 1;
    cout << "|";
    for (auto& Attribute : *Attributes) { //遍历所有属性

        int typesize = Attribute.charSize;
        string tem = str.substr(p, typesize);

        if (Attribute.dataType == 0) {

            int n = stoi(tem);
            cout.width(10);
            cout << n;
            cout << "|";
        }
        else if (Attribute.dataType == 1) {

            float f = stof(tem);
            cout.width(10);
            cout << f;
            cout << "|";

        }
        else {

            int k;
            for (k = 0;k < typesize;k++) {
                if (tem.at(k) != '!') break;
            }
            tem = tem.substr(k);
            cout.width(10);
            cout << tem;
            cout << "|";
        }
        p += typesize;
    }
    cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193

    查询

    /* Process the word "select" 只支持全列查找和where-and */
int Interpreter::execSelect(const string &text, int *shift) {
    // In case we need to select specific attributes later, use vector
    vector<string> attributes;
    string tableName;

    // Determine whether "*" exists
    string word = extractWord(text, shift);
    if (word != "*") {
        cout << "Syntax error for missing \"*\"" << endl;
        return 0;
    }
    attributes.push_back(word);

    // Determine whether "from" exists
    word = extractWord(text, shift);
    if (word != "from") {
        cout << "Syntax error for missing \"from\"" << endl;
        return 0;
    }

    word = extractWord(text, shift);
    tableName = word;

    // Determine whether the sentence is over
    word = extractWord(text, shift);
    // Sentence is over
    if (word == ";") {
        api->select(tableName, &attributes, nullptr);
        return 1;
    }
        // Conditional statement exists
    else if (word == "where") {
        vector<Condition> conditions;
        string attributeName;
        int operate;
        string value;

        // Extract all conditions
        do {
            word = extractWord(text, shift);
            attributeName = word;
            word = extractWord(text, shift);
            if (word == "=")
                operate = Condition::OPERATOR_EQUAL;
            else if (word == "<")
                operate = Condition::OPERATOR_LESS;
            else if (word == ">")
                operate = Condition::OPERATOR_MORE;
            else if (word == "<=")
                operate = Condition::OPERATOR_LESS_EQUAL;
            else if (word == ">=")
                operate = Condition::OPERATOR_MORE_EQUAL;
            else if (word == "<>")
                operate = Condition::OPERATOR_NOT_EQUAL;
            else {
                cout << "Syntax error for condition" << endl;
                return 0;
            }
            word = extractWord(text, shift);
            value = word;

            // Create and store the condition
            Condition condition(attributeName, operate, value);
            conditions.push_back(condition);

            word = extractWord(text, shift);
        } while (word == "and");

        // Determine whether the ";" exists
        if (word != ";") {
            cout << "Syntax error for no \";\"" << endl;
            return 0;
        }

        api->select(tableName, &attributes, &conditions);
        return 1;
    } else {
        cout << "Syntax error" << endl;
        return 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    void API::select(const string& tableName, vector<string>* attributeName, vector<Condition>* conditions) {

    vector<Attribute> attributes = getTableAttribute(tableName);

    if (conditions == nullptr) {
        //无条件，即全列全记录查询
        rm->PrintAllRecord(tableName, &attributes);
    }
    else {
        selectwithconditions(tableName, &attributes, conditions);
    }
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    void RecordManager::PrintAllRecord(string tablename, vector<Attribute>* Attributes)
{
    Block* btmp;
    int recordsize = getrecordsize(Attributes);
    string tablefilename = "../data/" + tablename + ".txt";

    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }

    int blocknum = bufferManager.GetFileSize(tablefilename);//文件块数
    string str;
    string tem;

    for (int i = 0;i < blocknum;i++) {//遍历块
        btmp = bufferManager.GetFileBlock(tablefilename, i);
        int recordnum = (btmp->GetSize() - 4) / recordsize;//块中记录数

        if (i == 0 && recordnum == 0) {
            cout << "The table is empty!" << endl;
            break;
        }

        for (int j = 0;j < recordnum;j++) {//遍历块中记录
            if (i == 0 & j == 0) {
                printouttablehead(Attributes);
            }
            int p = 1;
            str = (*(btmp->GetRecords(j, j + 1, recordsize)))[0];
            if (str.at(0) == '%') {

                cout << "|";
                for (auto& Attribute : *Attributes) { //遍历表中所有属性

                    int typesize = Attribute.charSize;
                    tem = str.substr(p, typesize);//取出记录中对应属性列的数据


                    if (Attribute.dataType == 0) {
                        int n = stoi(tem);
                        cout.width(10);
                        cout << n;
                        cout << "|";
                    }
                    else if (Attribute.dataType == 1) {
                        float f = stof(tem);
                        cout.width(10);
                        cout << f;
                        cout << "|";
                    }
                    else {
                        int k;
                        for (k = 0;k < typesize;k++) {
                            if (tem.at(k) != '!') break;
                        }
                        tem = tem.substr(k);
                        cout.width(10);
                        cout << tem;
                        cout << "|";
                    }
                    p = p + typesize;
                }
                cout << endl;
            }

        }
    }
}

//有where条件的查询
void API::selectwithconditions(string tablename, vector<Attribute>* Attributes, vector<Condition>* conditions)
{
    int n = conditions->size();
    int s = Attributes->size();
    int recordsize = rm->getrecordsize(Attributes);

    vector<RecordPosition> repo;

    int flag = 0;//标记是否找有索引
    int flag1 = 0;//标记是否找到相应记录

    vector<Condition> condwithouindex; //将没有index的conditions放在一起

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < s;j++) {
            if ((*conditions)[i].name == (*Attributes)[j].name)
            {
                if ((*Attributes)[j].index != "none" && flag == 0) {

                    repo = indexforcondition(tablename, (*Attributes)[j], (*conditions)[i].operate, (*conditions)[i].value); //在API里调用index搜索，返回有Index的查找条件对应数据所在位置

                    flag = 1;
                }
                else {

                    condwithouindex.push_back((*conditions)[i]);
                }

            }
        }
    }
    if (flag == 1) {

        flag1 = rm->selectwithoutindex(tablename, Attributes, &repo, &condwithouindex); //获得没有条件不在索引上的被筛选出数据的位置
    }

    else {
        flag1 = rm->selectbyorders(tablename, Attributes, conditions);

    }
    if (flag1 == 0)
    {
        cout << "No records!" << endl;
    }
}

int RecordManager::selectbyorders(string tablename, vector<Attribute>* Attributes, vector<Condition>* conditions)
{
    string tablefilename = "../data/" + tablename + ".txt";

    if (!bufferManager.IsFileRegistered(tablefilename)) {
        bufferManager.LoadFile(tablefilename);
    }

    int i = bufferManager.GetFileSize(tablefilename.c_str());  //block的数量
    Block* btmp;

    int flag = 0;
    int recordNum;
    int p = 0;
    int recordsize;
    recordsize = getrecordsize(Attributes);

    string putouts;

    for (int j = 0;j < i;j++)
    {
        btmp = bufferManager.GetFileBlock(tablefilename.c_str(), j);
        if (btmp == NULL) {
            cout << "The records don't exsit!" << endl;
        }
        recordNum = (btmp->GetSize() - 4) / recordsize;

        for (int k = 0;k < recordNum;k++) //第k+1条记录
        {
            putouts = (*(btmp->GetRecords(k, k + 1, recordsize)))[0];

            if (putouts.at(0) == '%') {

                if (isSatisfied(Attributes, &putouts, conditions)) {
                    if (flag == 0) printouttablehead(Attributes);
                        putout(putouts, Attributes);
                        flag = 1;
                }

            }
        }
    }

    return flag;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162

    B+树

    该项目的索引功能是通过B+树实现的，需要索引时从索引文件中读出索引信息构建B+树，之后B+树销毁，但是索引文件的块一直保存在内存中，如再需要索引就再从索引文件块中读取构建，直到析构BufferMananger时写回到索引文件

    BufferManager::~BufferManager(){
    SaveFile(TABLE_INFO_PATH);
    for(int i = 0; i < BUFFER_SIZE; i++){
        if(bufferPool[i]->dirty){
            fstream os ;
            os.open(bufferPool[i]->fileName);
            WriteBlockToDisk(os, bufferPool[i]->idx, bufferPool[i]->block->data);
            os.close();
        }
        delete bufferPool[i];
    }

    delete[]  bufferPool;
    delete freeBufferList;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在B+树结点类中有如下属性成员：

    bool isLeafNode;
uint32_t keyLength;//键长度
uint32_t dataCount;
uint32_t parent;//内部节点使用，指向父节点
uint32_t pageNum;

vector<keyType> keyVector;//键数组，若为内部节点用作分隔数据范围，若为叶子节点用作记录的键
vector<uint32_t> pageVector;//页数组，内部节点使用时，与keyVector对应，是子节点的数组。叶子节点使用时，尾结点为下一个叶子节点
vector<RecordPosition> recordVector;//记录数组，叶子节点使用，与keyVector对应，是记录（位置）的数组

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    B+树类属性成员：

    string indexFileName;
uint32_t keyLength;
uint32_t nodeCount;
uint32_t root;//根节点的页编号，也就是在索引文件的第几个块中
uint32_t freePageCount;
vector<uint32_t> freePages;//空闲页数组，当删除结点时存入，减少内存操作，提高B+树性能

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    gif演示B+树增删：

    插入：

    插入1

    插入-叶子分裂-父节点扩大

    插入-叶子节点分裂-父节点分裂

    插入-最大值

    删除：

    删除1

    删除-叶子合并

    删除-叶子合并-父节点更新

    删除-叶子节点兄弟补充

    删除-最大值

  • 相关阅读:
    刷题笔记之九（查找输入整数二进制中1的个数+完全数计算+杨辉三角的变形+计算某字符出现次数）
    Vue+NodeJS实现邮件发送
    Deep Joint Demosaicking and Denoising
    SpringMVC-接收请求中的json数据及日期类型参数传递
    用qt编译qmake
    Nevron Vision for .NET 2023.1 Crack
    Spring Security 前后端分离（前端篇）
    实再高度为设备高度的100%布局
    博科交换机使用
    什么牌子的电容笔性价比高？口碑好的电容笔推荐
  • 原文地址：https://blog.csdn.net/Falling_Asteroid/article/details/133638831