1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/art_node.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/execution/index/art/fixed_size_allocator.hpp"
12#include "duckdb/execution/index/art/swizzleable_pointer.hpp"
13
14namespace duckdb {
15
16// classes
17enum class NType : uint8_t {
18 PREFIX_SEGMENT = 1,
19 LEAF_SEGMENT = 2,
20 LEAF = 3,
21 NODE_4 = 4,
22 NODE_16 = 5,
23 NODE_48 = 6,
24 NODE_256 = 7
25};
26class ART;
27class Node;
28class Prefix;
29class MetaBlockReader;
30class MetaBlockWriter;
31
32// structs
33struct BlockPointer;
34struct ARTFlags;
35
36//! The ARTNode is the swizzleable pointer class of the ART index.
37//! If the ARTNode pointer is not swizzled, then the leftmost byte identifies the NType.
38//! The remaining bytes are the position in the respective ART buffer.
39class Node : public SwizzleablePointer {
40public:
41 // constants (this allows testing performance with different ART node sizes)
42
43 //! Node prefixes (NOTE: this should always hold: PREFIX_SEGMENT_SIZE >= PREFIX_INLINE_BYTES)
44 static constexpr uint32_t PREFIX_INLINE_BYTES = 8;
45 static constexpr uint32_t PREFIX_SEGMENT_SIZE = 32;
46 //! Node thresholds
47 static constexpr uint8_t NODE_48_SHRINK_THRESHOLD = 12;
48 static constexpr uint8_t NODE_256_SHRINK_THRESHOLD = 36;
49 //! Node sizes
50 static constexpr uint8_t NODE_4_CAPACITY = 4;
51 static constexpr uint8_t NODE_16_CAPACITY = 16;
52 static constexpr uint8_t NODE_48_CAPACITY = 48;
53 static constexpr uint16_t NODE_256_CAPACITY = 256;
54 //! Other constants
55 static constexpr uint8_t EMPTY_MARKER = 48;
56 static constexpr uint32_t LEAF_SEGMENT_SIZE = 8;
57
58public:
59 //! Constructs an empty ARTNode
60 Node();
61 //! Constructs a swizzled pointer from a block ID and an offset
62 explicit Node(MetaBlockReader &reader);
63 //! Get a new pointer to a node, might cause a new buffer allocation, and initialize it
64 static void New(ART &art, Node &node, const NType type);
65 //! Free the node (and its subtree)
66 static void Free(ART &art, Node &node);
67
68 inline bool operator==(const Node &node) const {
69 return swizzle_flag == node.swizzle_flag && type == node.type && offset == node.offset &&
70 buffer_id == node.buffer_id;
71 }
72
73 //! Retrieve the node type from the leftmost byte
74 inline NType DecodeARTNodeType() const {
75 D_ASSERT(!IsSwizzled());
76 D_ASSERT(type >= (uint8_t)NType::PREFIX_SEGMENT);
77 D_ASSERT(type <= (uint8_t)NType::NODE_256);
78 return NType(type);
79 }
80
81 //! Set the pointer
82 inline void SetPtr(const SwizzleablePointer ptr) {
83 swizzle_flag = ptr.swizzle_flag;
84 type = ptr.type;
85 offset = ptr.offset;
86 buffer_id = ptr.buffer_id;
87 }
88
89 //! Replace the child node at the respective byte
90 void ReplaceChild(const ART &art, const uint8_t byte, const Node child);
91 //! Insert the child node at byte
92 static void InsertChild(ART &art, Node &node, const uint8_t byte, const Node child);
93 //! Delete the child node at the respective byte
94 static void DeleteChild(ART &art, Node &node, const uint8_t byte);
95
96 //! Get the child for the respective byte in the node
97 optional_ptr<Node> GetChild(ART &art, const uint8_t byte) const;
98 //! Get the first child that is greater or equal to the specific byte
99 optional_ptr<Node> GetNextChild(ART &art, uint8_t &byte, const bool deserialize = true) const;
100
101 //! Serialize the node
102 BlockPointer Serialize(ART &art, MetaBlockWriter &writer);
103 //! Deserialize the node
104 void Deserialize(ART &art);
105
106 //! Returns the string representation of the node, or only traverses and verifies the node and its subtree
107 string VerifyAndToString(ART &art, const bool only_verify);
108 //! Returns the capacity of the node
109 idx_t GetCapacity() const;
110 //! Returns a pointer to the prefix of the node
111 Prefix &GetPrefix(ART &art);
112 //! Returns the matching node type for a given count
113 static NType GetARTNodeTypeByCount(const idx_t count);
114 //! Get references to the different allocators
115 static FixedSizeAllocator &GetAllocator(const ART &art, NType type);
116
117 //! Initializes a merge by fully deserializing the subtree of the node and incrementing its buffer IDs
118 void InitializeMerge(ART &art, const ARTFlags &flags);
119 //! Merge another node into this node
120 bool Merge(ART &art, Node &other);
121 //! Merge two nodes by first resolving their prefixes
122 bool ResolvePrefixes(ART &art, Node &other);
123 //! Merge two nodes that have no prefix or the same prefix
124 bool MergeInternal(ART &art, Node &other);
125
126 //! Vacuum all nodes that exceed their respective vacuum thresholds
127 static void Vacuum(ART &art, Node &node, const ARTFlags &flags);
128};
129
130} // namespace duckdb
131