v22-0010-Reduce-node4-to-node3.patch

From dfa2aece9d83cc6e9ab791c6b1641aca1d02d8f6 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Fri, 20 Jan 2023 18:05:15 +0700
Subject: [PATCH v22 10/22] Reduce node4 to node3

Now that we don't store "chunk", the base node type is only
5 bytes in size. With 3 key chunks, There is no alignment
padding between the chunks array and the child/value array.
This reduces the smallest inner node to 32 bytes on 64-bit
platforms.
---
 src/include/lib/radixtree.h             | 124 ++++++++++++------------
 src/include/lib/radixtree_delete_impl.h |  20 ++--
 src/include/lib/radixtree_insert_impl.h |  38 ++++----
 src/include/lib/radixtree_iter_impl.h   |  18 ++--
 src/include/lib/radixtree_search_impl.h |  18 ++--
 5 files changed, 109 insertions(+), 109 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index d15ea8f0fe..6cc8442c89 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -136,9 +136,9 @@
 #define RT_REPLACE_NODE RT_MAKE_NAME(replace_node)
 #define RT_PTR_GET_LOCAL RT_MAKE_NAME(ptr_get_local)
 #define RT_PTR_ALLOC_IS_VALID RT_MAKE_NAME(ptr_stored_is_valid)
-#define RT_NODE_4_SEARCH_EQ RT_MAKE_NAME(node_4_search_eq)
+#define RT_NODE_3_SEARCH_EQ RT_MAKE_NAME(node_3_search_eq)
 #define RT_NODE_32_SEARCH_EQ RT_MAKE_NAME(node_32_search_eq)
-#define RT_NODE_4_GET_INSERTPOS RT_MAKE_NAME(node_4_get_insertpos)
+#define RT_NODE_3_GET_INSERTPOS RT_MAKE_NAME(node_3_get_insertpos)
 #define RT_NODE_32_GET_INSERTPOS RT_MAKE_NAME(node_32_get_insertpos)
 #define RT_CHUNK_CHILDREN_ARRAY_SHIFT RT_MAKE_NAME(chunk_children_array_shift)
 #define RT_CHUNK_VALUES_ARRAY_SHIFT RT_MAKE_NAME(chunk_values_array_shift)
@@ -181,22 +181,22 @@
 #endif
 #define RT_NODE RT_MAKE_NAME(node)
 #define RT_NODE_ITER RT_MAKE_NAME(node_iter)
-#define RT_NODE_BASE_4 RT_MAKE_NAME(node_base_4)
+#define RT_NODE_BASE_3 RT_MAKE_NAME(node_base_3)
 #define RT_NODE_BASE_32 RT_MAKE_NAME(node_base_32)
 #define RT_NODE_BASE_125 RT_MAKE_NAME(node_base_125)
 #define RT_NODE_BASE_256 RT_MAKE_NAME(node_base_256)
-#define RT_NODE_INNER_4 RT_MAKE_NAME(node_inner_4)
+#define RT_NODE_INNER_3 RT_MAKE_NAME(node_inner_3)
 #define RT_NODE_INNER_32 RT_MAKE_NAME(node_inner_32)
 #define RT_NODE_INNER_125 RT_MAKE_NAME(node_inner_125)
 #define RT_NODE_INNER_256 RT_MAKE_NAME(node_inner_256)
-#define RT_NODE_LEAF_4 RT_MAKE_NAME(node_leaf_4)
+#define RT_NODE_LEAF_3 RT_MAKE_NAME(node_leaf_3)
 #define RT_NODE_LEAF_32 RT_MAKE_NAME(node_leaf_32)
 #define RT_NODE_LEAF_125 RT_MAKE_NAME(node_leaf_125)
 #define RT_NODE_LEAF_256 RT_MAKE_NAME(node_leaf_256)
 #define RT_SIZE_CLASS RT_MAKE_NAME(size_class)
 #define RT_SIZE_CLASS_ELEM RT_MAKE_NAME(size_class_elem)
 #define RT_SIZE_CLASS_INFO RT_MAKE_NAME(size_class_info)
-#define RT_CLASS_4_FULL RT_MAKE_NAME(class_4_full)
+#define RT_CLASS_3_FULL RT_MAKE_NAME(class_3_full)
 #define RT_CLASS_32_PARTIAL RT_MAKE_NAME(class_32_partial)
 #define RT_CLASS_32_FULL RT_MAKE_NAME(class_32_full)
 #define RT_CLASS_125_FULL RT_MAKE_NAME(class_125_full)
@@ -305,7 +305,7 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree);
  * allocator padding in both the inner and leaf nodes on DSA.
  * node
  */
-#define RT_NODE_KIND_4			0x00
+#define RT_NODE_KIND_3			0x00
 #define RT_NODE_KIND_32			0x01
 #define RT_NODE_KIND_125		0x02
 #define RT_NODE_KIND_256		0x03
@@ -323,7 +323,7 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree);
 
 typedef enum RT_SIZE_CLASS
 {
-	RT_CLASS_4_FULL = 0,
+	RT_CLASS_3_FULL = 0,
 	RT_CLASS_32_PARTIAL,
 	RT_CLASS_32_FULL,
 	RT_CLASS_125_FULL,
@@ -387,13 +387,13 @@ typedef struct RT_NODE
 /* Base type of each node kinds for leaf and inner nodes */
 /* The base types must be a be able to accommodate the largest size
 class for variable-sized node kinds*/
-typedef struct RT_NODE_BASE_4
+typedef struct RT_NODE_BASE_3
 {
 	RT_NODE		n;
 
-	/* 4 children, for key chunks */
-	uint8		chunks[4];
-} RT_NODE_BASE_4;
+	/* 3 children, for key chunks */
+	uint8		chunks[3];
+} RT_NODE_BASE_3;
 
 typedef struct RT_NODE_BASE_32
 {
@@ -437,21 +437,21 @@ typedef struct RT_NODE_BASE_256
  * good. It might be better to just indicate non-existing entries the same way
  * in inner nodes.
  */
-typedef struct RT_NODE_INNER_4
+typedef struct RT_NODE_INNER_3
 {
-	RT_NODE_BASE_4 base;
+	RT_NODE_BASE_3 base;
 
 	/* number of children depends on size class */
 	RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER];
-} RT_NODE_INNER_4;
+} RT_NODE_INNER_3;
 
-typedef struct RT_NODE_LEAF_4
+typedef struct RT_NODE_LEAF_3
 {
-	RT_NODE_BASE_4 base;
+	RT_NODE_BASE_3 base;
 
 	/* number of values depends on size class */
 	RT_VALUE_TYPE	values[FLEXIBLE_ARRAY_MEMBER];
-} RT_NODE_LEAF_4;
+} RT_NODE_LEAF_3;
 
 typedef struct RT_NODE_INNER_32
 {
@@ -520,11 +520,11 @@ typedef struct RT_SIZE_CLASS_ELEM
 } RT_SIZE_CLASS_ELEM;
 
 static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = {
-	[RT_CLASS_4_FULL] = {
-		.name = "radix tree node 4",
-		.fanout = 4,
-		.inner_size = sizeof(RT_NODE_INNER_4) + 4 * sizeof(RT_PTR_ALLOC),
-		.leaf_size = sizeof(RT_NODE_LEAF_4) + 4 * sizeof(RT_VALUE_TYPE),
+	[RT_CLASS_3_FULL] = {
+		.name = "radix tree node 3",
+		.fanout = 3,
+		.inner_size = sizeof(RT_NODE_INNER_3) + 3 * sizeof(RT_PTR_ALLOC),
+		.leaf_size = sizeof(RT_NODE_LEAF_3) + 3 * sizeof(RT_VALUE_TYPE),
 	},
 	[RT_CLASS_32_PARTIAL] = {
 		.name = "radix tree node 15",
@@ -556,7 +556,7 @@ static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = {
 
 /* Map from the node kind to its minimum size class */
 static const RT_SIZE_CLASS RT_KIND_MIN_SIZE_CLASS[RT_NODE_KIND_COUNT] = {
-	[RT_NODE_KIND_4] = RT_CLASS_4_FULL,
+	[RT_NODE_KIND_3] = RT_CLASS_3_FULL,
 	[RT_NODE_KIND_32] = RT_CLASS_32_PARTIAL,
 	[RT_NODE_KIND_125] = RT_CLASS_125_FULL,
 	[RT_NODE_KIND_256] = RT_CLASS_256,
@@ -673,7 +673,7 @@ RT_PTR_ALLOC_IS_VALID(RT_PTR_ALLOC ptr)
  * if there is no such element.
  */
 static inline int
-RT_NODE_4_SEARCH_EQ(RT_NODE_BASE_4 *node, uint8 chunk)
+RT_NODE_3_SEARCH_EQ(RT_NODE_BASE_3 *node, uint8 chunk)
 {
 	int			idx = -1;
 
@@ -693,7 +693,7 @@ RT_NODE_4_SEARCH_EQ(RT_NODE_BASE_4 *node, uint8 chunk)
  * Return index of the chunk to insert into chunks in the given node.
  */
 static inline int
-RT_NODE_4_GET_INSERTPOS(RT_NODE_BASE_4 *node, uint8 chunk)
+RT_NODE_3_GET_INSERTPOS(RT_NODE_BASE_3 *node, uint8 chunk)
 {
 	int			idx;
 
@@ -810,7 +810,7 @@ RT_NODE_32_GET_INSERTPOS(RT_NODE_BASE_32 *node, uint8 chunk)
 
 /*
  * Functions to manipulate both chunks array and children/values array.
- * These are used for node-4 and node-32.
+ * These are used for node-3 and node-32.
  */
 
 /* Shift the elements right at 'idx' by one */
@@ -848,7 +848,7 @@ static inline void
 RT_CHUNK_CHILDREN_ARRAY_COPY(uint8 *src_chunks, RT_PTR_ALLOC *src_children,
 						  uint8 *dst_chunks, RT_PTR_ALLOC *dst_children)
 {
-	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_4_FULL].fanout;
+	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout;
 	const Size chunk_size = sizeof(uint8) * fanout;
 	const Size children_size = sizeof(RT_PTR_ALLOC) * fanout;
 
@@ -860,7 +860,7 @@ static inline void
 RT_CHUNK_VALUES_ARRAY_COPY(uint8 *src_chunks, RT_VALUE_TYPE *src_values,
 						uint8 *dst_chunks, RT_VALUE_TYPE *dst_values)
 {
-	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_4_FULL].fanout;
+	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout;
 	const Size chunk_size = sizeof(uint8) * fanout;
 	const Size values_size = sizeof(RT_VALUE_TYPE) * fanout;
 
@@ -1060,9 +1060,9 @@ RT_NEW_ROOT(RT_RADIX_TREE *tree, uint64 key)
 	RT_PTR_ALLOC allocnode;
 	RT_PTR_LOCAL newnode;
 
-	allocnode = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, inner);
+	allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner);
 	newnode = RT_PTR_GET_LOCAL(tree, allocnode);
-	RT_INIT_NODE(newnode, RT_NODE_KIND_4, RT_CLASS_4_FULL, inner);
+	RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner);
 	newnode->shift = shift;
 	tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(shift);
 	tree->ctl->root = allocnode;
@@ -1183,17 +1183,17 @@ RT_EXTEND(RT_RADIX_TREE *tree, uint64 key)
 	{
 		RT_PTR_ALLOC	allocnode;
 		RT_PTR_LOCAL	node;
-		RT_NODE_INNER_4 *n4;
+		RT_NODE_INNER_3 *n3;
 
-		allocnode = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, true);
+		allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, true);
 		node = RT_PTR_GET_LOCAL(tree, allocnode);
-		RT_INIT_NODE(node, RT_NODE_KIND_4, RT_CLASS_4_FULL, true);
+		RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3_FULL, true);
 		node->shift = shift;
 		node->count = 1;
 
-		n4 = (RT_NODE_INNER_4 *) node;
-		n4->base.chunks[0] = 0;
-		n4->children[0] = tree->ctl->root;
+		n3 = (RT_NODE_INNER_3 *) node;
+		n3->base.chunks[0] = 0;
+		n3->children[0] = tree->ctl->root;
 
 		/* Update the root */
 		tree->ctl->root = allocnode;
@@ -1223,9 +1223,9 @@ RT_SET_EXTEND(RT_RADIX_TREE *tree, uint64 key, RT_VALUE_TYPE value, RT_PTR_LOCAL
 		int			newshift = shift - RT_NODE_SPAN;
 		bool		inner = newshift > 0;
 
-		allocchild = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, inner);
+		allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner);
 		newchild = RT_PTR_GET_LOCAL(tree, allocchild);
-		RT_INIT_NODE(newchild, RT_NODE_KIND_4, RT_CLASS_4_FULL, inner);
+		RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner);
 		newchild->shift = newshift;
 		RT_NODE_INSERT_INNER(tree, parent, stored_node, node, key, allocchild);
 
@@ -1430,12 +1430,12 @@ RT_FREE_RECURSE(RT_RADIX_TREE *tree, RT_PTR_ALLOC ptr)
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE_INNER_4 *n4 = (RT_NODE_INNER_4 *) node;
+				RT_NODE_INNER_3 *n3 = (RT_NODE_INNER_3 *) node;
 
-				for (int i = 0; i < n4->base.n.count; i++)
-					RT_FREE_RECURSE(tree, n4->children[i]);
+				for (int i = 0; i < n3->base.n.count; i++)
+					RT_FREE_RECURSE(tree, n3->children[i]);
 
 				break;
 			}
@@ -1892,12 +1892,12 @@ RT_VERIFY_NODE(RT_PTR_LOCAL node)
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE_BASE_4 *n4 = (RT_NODE_BASE_4 *) node;
+				RT_NODE_BASE_3 *n3 = (RT_NODE_BASE_3 *) node;
 
-				for (int i = 1; i < n4->n.count; i++)
-					Assert(n4->chunks[i - 1] < n4->chunks[i]);
+				for (int i = 1; i < n3->n.count; i++)
+					Assert(n3->chunks[i - 1] < n3->chunks[i]);
 
 				break;
 			}
@@ -1959,10 +1959,10 @@ RT_VERIFY_NODE(RT_PTR_LOCAL node)
 RT_SCOPE void
 RT_STATS(RT_RADIX_TREE *tree)
 {
-	ereport(NOTICE, (errmsg("num_keys = " UINT64_FORMAT ", height = %d, n4 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u",
+	ereport(NOTICE, (errmsg("num_keys = " UINT64_FORMAT ", height = %d, n3 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u",
 						 tree->ctl->num_keys,
 						 tree->ctl->root->shift / RT_NODE_SPAN,
-						 tree->ctl->cnt[RT_CLASS_4_FULL],
+						 tree->ctl->cnt[RT_CLASS_3_FULL],
 						 tree->ctl->cnt[RT_CLASS_32_PARTIAL],
 						 tree->ctl->cnt[RT_CLASS_32_FULL],
 						 tree->ctl->cnt[RT_CLASS_125_FULL],
@@ -1977,7 +1977,7 @@ RT_DUMP_NODE(RT_PTR_LOCAL node, int level, bool recurse)
 
 	fprintf(stderr, "[%s] kind %d, fanout %d, count %u, shift %u:\n",
 			NODE_IS_LEAF(node) ? "LEAF" : "INNR",
-			(node->kind == RT_NODE_KIND_4) ? 4 :
+			(node->kind == RT_NODE_KIND_3) ? 3 :
 			(node->kind == RT_NODE_KIND_32) ? 32 :
 			(node->kind == RT_NODE_KIND_125) ? 125 : 256,
 			node->fanout == 0 ? 256 : node->fanout,
@@ -1988,26 +1988,26 @@ RT_DUMP_NODE(RT_PTR_LOCAL node, int level, bool recurse)
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
 				for (int i = 0; i < node->count; i++)
 				{
 					if (NODE_IS_LEAF(node))
 					{
-						RT_NODE_LEAF_4 *n4 = (RT_NODE_LEAF_4 *) node;
+						RT_NODE_LEAF_3 *n3 = (RT_NODE_LEAF_3 *) node;
 
 						fprintf(stderr, "%schunk 0x%X value 0x" UINT64_FORMAT_HEX "\n",
-								space, n4->base.chunks[i], (uint64) n4->values[i]);
+								space, n3->base.chunks[i], (uint64) n3->values[i]);
 					}
 					else
 					{
-						RT_NODE_INNER_4 *n4 = (RT_NODE_INNER_4 *) node;
+						RT_NODE_INNER_3 *n3 = (RT_NODE_INNER_3 *) node;
 
 						fprintf(stderr, "%schunk 0x%X ->",
-								space, n4->base.chunks[i]);
+								space, n3->base.chunks[i]);
 
 						if (recurse)
-							RT_DUMP_NODE(n4->children[i], level + 1, recurse);
+							RT_DUMP_NODE(n3->children[i], level + 1, recurse);
 						else
 							fprintf(stderr, "\n");
 					}
@@ -2229,22 +2229,22 @@ RT_DUMP(RT_RADIX_TREE *tree)
 #undef RT_ITER
 #undef RT_NODE
 #undef RT_NODE_ITER
-#undef RT_NODE_BASE_4
+#undef RT_NODE_BASE_3
 #undef RT_NODE_BASE_32
 #undef RT_NODE_BASE_125
 #undef RT_NODE_BASE_256
-#undef RT_NODE_INNER_4
+#undef RT_NODE_INNER_3
 #undef RT_NODE_INNER_32
 #undef RT_NODE_INNER_125
 #undef RT_NODE_INNER_256
-#undef RT_NODE_LEAF_4
+#undef RT_NODE_LEAF_3
 #undef RT_NODE_LEAF_32
 #undef RT_NODE_LEAF_125
 #undef RT_NODE_LEAF_256
 #undef RT_SIZE_CLASS
 #undef RT_SIZE_CLASS_ELEM
 #undef RT_SIZE_CLASS_INFO
-#undef RT_CLASS_4_FULL
+#undef RT_CLASS_3_FULL
 #undef RT_CLASS_32_PARTIAL
 #undef RT_CLASS_32_FULL
 #undef RT_CLASS_125_FULL
@@ -2282,9 +2282,9 @@ RT_DUMP(RT_RADIX_TREE *tree)
 #undef RT_REPLACE_NODE
 #undef RT_PTR_GET_LOCAL
 #undef RT_PTR_ALLOC_IS_VALID
-#undef RT_NODE_4_SEARCH_EQ
+#undef RT_NODE_3_SEARCH_EQ
 #undef RT_NODE_32_SEARCH_EQ
-#undef RT_NODE_4_GET_INSERTPOS
+#undef RT_NODE_3_GET_INSERTPOS
 #undef RT_NODE_32_GET_INSERTPOS
 #undef RT_CHUNK_CHILDREN_ARRAY_SHIFT
 #undef RT_CHUNK_VALUES_ARRAY_SHIFT
diff --git a/src/include/lib/radixtree_delete_impl.h b/src/include/lib/radixtree_delete_impl.h
index 2f1c172672..b9f07f4eb5 100644
--- a/src/include/lib/radixtree_delete_impl.h
+++ b/src/include/lib/radixtree_delete_impl.h
@@ -1,12 +1,12 @@
 /* TODO: shrink nodes */
 
 #if defined(RT_NODE_LEVEL_INNER)
-#define RT_NODE4_TYPE RT_NODE_INNER_4
+#define RT_NODE3_TYPE RT_NODE_INNER_3
 #define RT_NODE32_TYPE RT_NODE_INNER_32
 #define RT_NODE125_TYPE RT_NODE_INNER_125
 #define RT_NODE256_TYPE RT_NODE_INNER_256
 #elif defined(RT_NODE_LEVEL_LEAF)
-#define RT_NODE4_TYPE RT_NODE_LEAF_4
+#define RT_NODE3_TYPE RT_NODE_LEAF_3
 #define RT_NODE32_TYPE RT_NODE_LEAF_32
 #define RT_NODE125_TYPE RT_NODE_LEAF_125
 #define RT_NODE256_TYPE RT_NODE_LEAF_256
@@ -24,20 +24,20 @@
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node;
-				int			idx = RT_NODE_4_SEARCH_EQ((RT_NODE_BASE_4 *) n4, chunk);
+				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node;
+				int			idx = RT_NODE_3_SEARCH_EQ((RT_NODE_BASE_3 *) n3, chunk);
 
 				if (idx < 0)
 					return false;
 
 #ifdef RT_NODE_LEVEL_LEAF
-				RT_CHUNK_VALUES_ARRAY_DELETE(n4->base.chunks, n4->values,
-										  n4->base.n.count, idx);
+				RT_CHUNK_VALUES_ARRAY_DELETE(n3->base.chunks, n3->values,
+										  n3->base.n.count, idx);
 #else
-				RT_CHUNK_CHILDREN_ARRAY_DELETE(n4->base.chunks, n4->children,
-											n4->base.n.count, idx);
+				RT_CHUNK_CHILDREN_ARRAY_DELETE(n3->base.chunks, n3->children,
+											n3->base.n.count, idx);
 #endif
 				break;
 			}
@@ -100,7 +100,7 @@
 
 	return true;
 
-#undef RT_NODE4_TYPE
+#undef RT_NODE3_TYPE
 #undef RT_NODE32_TYPE
 #undef RT_NODE125_TYPE
 #undef RT_NODE256_TYPE
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
index 90fe5f539e..16461bdb03 100644
--- a/src/include/lib/radixtree_insert_impl.h
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -1,10 +1,10 @@
 #if defined(RT_NODE_LEVEL_INNER)
-#define RT_NODE4_TYPE RT_NODE_INNER_4
+#define RT_NODE3_TYPE RT_NODE_INNER_3
 #define RT_NODE32_TYPE RT_NODE_INNER_32
 #define RT_NODE125_TYPE RT_NODE_INNER_125
 #define RT_NODE256_TYPE RT_NODE_INNER_256
 #elif defined(RT_NODE_LEVEL_LEAF)
-#define RT_NODE4_TYPE RT_NODE_LEAF_4
+#define RT_NODE3_TYPE RT_NODE_LEAF_3
 #define RT_NODE32_TYPE RT_NODE_LEAF_32
 #define RT_NODE125_TYPE RT_NODE_LEAF_125
 #define RT_NODE256_TYPE RT_NODE_LEAF_256
@@ -25,25 +25,25 @@
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node;
+				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node;
 				int			idx;
 
-				idx = RT_NODE_4_SEARCH_EQ(&n4->base, chunk);
+				idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk);
 				if (idx != -1)
 				{
 					/* found the existing chunk */
 					chunk_exists = true;
 #ifdef RT_NODE_LEVEL_LEAF
-					n4->values[idx] = value;
+					n3->values[idx] = value;
 #else
-					n4->children[idx] = child;
+					n3->children[idx] = child;
 #endif
 					break;
 				}
 
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4)))
+				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n3)))
 				{
 					RT_PTR_ALLOC allocnode;
 					RT_PTR_LOCAL newnode;
@@ -51,16 +51,16 @@
 					const uint8 new_kind = RT_NODE_KIND_32;
 					const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind];
 
-					/* grow node from 4 to 32 */
+					/* grow node from 3 to 32 */
 					allocnode = RT_ALLOC_NODE(tree, new_class, inner);
 					newnode = RT_SWITCH_NODE_KIND(tree, allocnode, node, new_kind, new_class, inner);
 					new32 = (RT_NODE32_TYPE *) newnode;
 
 #ifdef RT_NODE_LEVEL_LEAF
-					RT_CHUNK_VALUES_ARRAY_COPY(n4->base.chunks, n4->values,
+					RT_CHUNK_VALUES_ARRAY_COPY(n3->base.chunks, n3->values,
 											  new32->base.chunks, new32->values);
 #else
-					RT_CHUNK_CHILDREN_ARRAY_COPY(n4->base.chunks, n4->children,
+					RT_CHUNK_CHILDREN_ARRAY_COPY(n3->base.chunks, n3->children,
 											  new32->base.chunks, new32->children);
 #endif
 					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
@@ -68,27 +68,27 @@
 				}
 				else
 				{
-					int			insertpos = RT_NODE_4_GET_INSERTPOS(&n4->base, chunk);
-					int			count = n4->base.n.count;
+					int			insertpos = RT_NODE_3_GET_INSERTPOS(&n3->base, chunk);
+					int			count = n3->base.n.count;
 
 					/* shift chunks and children */
 					if (insertpos < count)
 					{
 						Assert(count > 0);
 #ifdef RT_NODE_LEVEL_LEAF
-						RT_CHUNK_VALUES_ARRAY_SHIFT(n4->base.chunks, n4->values,
+						RT_CHUNK_VALUES_ARRAY_SHIFT(n3->base.chunks, n3->values,
 												   count, insertpos);
 #else
-						RT_CHUNK_CHILDREN_ARRAY_SHIFT(n4->base.chunks, n4->children,
+						RT_CHUNK_CHILDREN_ARRAY_SHIFT(n3->base.chunks, n3->children,
 												   count, insertpos);
 #endif
 					}
 
-					n4->base.chunks[insertpos] = chunk;
+					n3->base.chunks[insertpos] = chunk;
 #ifdef RT_NODE_LEVEL_LEAF
-					n4->values[insertpos] = value;
+					n3->values[insertpos] = value;
 #else
-					n4->children[insertpos] = child;
+					n3->children[insertpos] = child;
 #endif
 					break;
 				}
@@ -304,7 +304,7 @@
 
 	return chunk_exists;
 
-#undef RT_NODE4_TYPE
+#undef RT_NODE3_TYPE
 #undef RT_NODE32_TYPE
 #undef RT_NODE125_TYPE
 #undef RT_NODE256_TYPE
diff --git a/src/include/lib/radixtree_iter_impl.h b/src/include/lib/radixtree_iter_impl.h
index 5c06f8b414..c428531438 100644
--- a/src/include/lib/radixtree_iter_impl.h
+++ b/src/include/lib/radixtree_iter_impl.h
@@ -1,10 +1,10 @@
 #if defined(RT_NODE_LEVEL_INNER)
-#define RT_NODE4_TYPE RT_NODE_INNER_4
+#define RT_NODE3_TYPE RT_NODE_INNER_3
 #define RT_NODE32_TYPE RT_NODE_INNER_32
 #define RT_NODE125_TYPE RT_NODE_INNER_125
 #define RT_NODE256_TYPE RT_NODE_INNER_256
 #elif defined(RT_NODE_LEVEL_LEAF)
-#define RT_NODE4_TYPE RT_NODE_LEAF_4
+#define RT_NODE3_TYPE RT_NODE_LEAF_3
 #define RT_NODE32_TYPE RT_NODE_LEAF_32
 #define RT_NODE125_TYPE RT_NODE_LEAF_125
 #define RT_NODE256_TYPE RT_NODE_LEAF_256
@@ -31,19 +31,19 @@
 
 	switch (node_iter->node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node_iter->node;
+				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node_iter->node;
 
 				node_iter->current_idx++;
-				if (node_iter->current_idx >= n4->base.n.count)
+				if (node_iter->current_idx >= n3->base.n.count)
 					break;
 #ifdef RT_NODE_LEVEL_LEAF
-				value = n4->values[node_iter->current_idx];
+				value = n3->values[node_iter->current_idx];
 #else
-				child = RT_PTR_GET_LOCAL(iter->tree, n4->children[node_iter->current_idx]);
+				child = RT_PTR_GET_LOCAL(iter->tree, n3->children[node_iter->current_idx]);
 #endif
-				key_chunk = n4->base.chunks[node_iter->current_idx];
+				key_chunk = n3->base.chunks[node_iter->current_idx];
 				found = true;
 				break;
 			}
@@ -132,7 +132,7 @@
 	return child;
 #endif
 
-#undef RT_NODE4_TYPE
+#undef RT_NODE3_TYPE
 #undef RT_NODE32_TYPE
 #undef RT_NODE125_TYPE
 #undef RT_NODE256_TYPE
diff --git a/src/include/lib/radixtree_search_impl.h b/src/include/lib/radixtree_search_impl.h
index d2bbdd2450..31138b6a72 100644
--- a/src/include/lib/radixtree_search_impl.h
+++ b/src/include/lib/radixtree_search_impl.h
@@ -1,10 +1,10 @@
 #if defined(RT_NODE_LEVEL_INNER)
-#define RT_NODE4_TYPE RT_NODE_INNER_4
+#define RT_NODE3_TYPE RT_NODE_INNER_3
 #define RT_NODE32_TYPE RT_NODE_INNER_32
 #define RT_NODE125_TYPE RT_NODE_INNER_125
 #define RT_NODE256_TYPE RT_NODE_INNER_256
 #elif defined(RT_NODE_LEVEL_LEAF)
-#define RT_NODE4_TYPE RT_NODE_LEAF_4
+#define RT_NODE3_TYPE RT_NODE_LEAF_3
 #define RT_NODE32_TYPE RT_NODE_LEAF_32
 #define RT_NODE125_TYPE RT_NODE_LEAF_125
 #define RT_NODE256_TYPE RT_NODE_LEAF_256
@@ -27,22 +27,22 @@
 
 	switch (node->kind)
 	{
-		case RT_NODE_KIND_4:
+		case RT_NODE_KIND_3:
 			{
-				RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node;
-				int			idx = RT_NODE_4_SEARCH_EQ((RT_NODE_BASE_4 *) n4, chunk);
+				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node;
+				int			idx = RT_NODE_3_SEARCH_EQ((RT_NODE_BASE_3 *) n3, chunk);
 
 #ifdef RT_ACTION_UPDATE
 				Assert(idx >= 0);
-				n4->children[idx] = new_child;
+				n3->children[idx] = new_child;
 #else
 				if (idx < 0)
 					return false;
 
 #ifdef RT_NODE_LEVEL_LEAF
-				value = n4->values[idx];
+				value = n3->values[idx];
 #else
-				child = n4->children[idx];
+				child = n3->children[idx];
 #endif
 #endif							/* RT_ACTION_UPDATE */
 				break;
@@ -125,7 +125,7 @@
 	return true;
 #endif							/* RT_ACTION_UPDATE */
 
-#undef RT_NODE4_TYPE
+#undef RT_NODE3_TYPE
 #undef RT_NODE32_TYPE
 #undef RT_NODE125_TYPE
 #undef RT_NODE256_TYPE
-- 
2.39.0