BPlusTree/bplus_tree.h at master · bhhbazinga/BPlusTree · GitHub

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
#ifndef BPLUS_TREE_H
#define BPLUS_TREE_H

#include <cstdio>
#include <string>
#include <vector>

#define DEBUG

#ifdef DEBUG
#define LOG(fmt, ...)                                               \
  do {                                                              \
    fprintf(stderr, "%s:%d:" fmt, __FILE__, __LINE__, __VA_ARGS__); \
  } while (0)

#define LOG2(fmt, ...)                 \
  do {                                 \
    fprintf(stderr, fmt, __VA_ARGS__); \
  } while (0)
#endif

class BPlusTree {
  struct Meta;
  struct Index;
  struct Record;
  struct Node;
  struct IndexNode;
  struct LeafNode;
  class BlockCache;

 public:
  BPlusTree(const char* path);
  ~BPlusTree();

  void Put(const std::string& key, const std::string& value);
  bool Delete(const std::string& key);
  bool Get(const std::string& key, std::string& value) const;
  std::vector<std::pair<std::string, std::string>> GetRange(
      const std::string& left_key, const std::string& right_key) const;
  bool Empty() const;
  size_t Size() const;

#ifdef DEBUG
  void Dump();
#endif

 private:
  template <typename T>
  T* Map(off_t offset) const;
  template <typename T>
  void UnMap(T* map_obj) const;
  template <typename T>
  T* Alloc();
  template <typename T>
  void Dealloc(T* node);

  constexpr size_t GetMinKeys() const;
  constexpr size_t GetMaxKeys() const;

  template <typename T>
  int UpperBound(T arr[], int n, const char* target) const;
  template <typename T>
  int LowerBound(T arr[], int n, const char* target) const;

  off_t GetLeafOffset(const char* key) const;
  LeafNode* SplitLeafNode(LeafNode* leaf_node);
  IndexNode* SplitIndexNode(IndexNode* index_node);
  size_t InsertKeyIntoIndexNode(IndexNode* index_node, const char* key,
                                Node* left_node, Node* right_node);
  size_t InsertKVIntoLeafNode(LeafNode* leaf_node, const char* key,
                              const char* value);
  int GetIndexFromLeafNode(LeafNode* leaf_node, const char* key) const;
  IndexNode* GetOrCreateParent(Node* node);

  bool BorrowFromLeftLeafSibling(LeafNode* leaf_node);
  bool BorrowFromRightLeafSibling(LeafNode* leaf_node);
  bool BorrowFromLeafSibling(LeafNode* leaf_node);
  bool MergeLeftLeaf(LeafNode* leaf_node);
  bool MergeRightLeaf(LeafNode* leaf_node);
  LeafNode* MergeLeaf(LeafNode* leaf_node);

  bool BorrowFromLeftIndexSibling(IndexNode* index_node);
  bool BorrowFromRightIndexSibling(IndexNode* index_node);
  bool BorrowFromIndexSibling(IndexNode* index_node);
  bool MergeLeftIndex(IndexNode* index_node);
  bool MergeRightIndex(IndexNode* index_node);
  IndexNode* MergeIndex(IndexNode* index_node);

  int fd_;
  BlockCache* block_cache_;
  Meta* meta_;
};

#endif  // BPLUS_TREE_H