diff --git a/ebtree/eb64tree.h b/ebtree/eb64tree.h
index 9c8feeb..ff2feee 100644
--- a/ebtree/eb64tree.h
+++ b/ebtree/eb64tree.h
@@ -38,11 +38,16 @@
  * eb_node so that it can be cast into an eb_node. We could also have put some
  * sort of transparent union here to reduce the indirection level, but the fact
  * is, the end user is not meant to manipulate internals, so this is pointless.
+ * In case sizeof(void*)>=sizeof(u64), we know there will be some padding after
+ * the key if it's unaligned. In this case we force the alignment on void* so
+ * that we prefer to have the padding before for more efficient accesses.
  */
 struct eb64_node {
 	struct eb_node node; /* the tree node, must be at the beginning */
+	MAYBE_ALIGN(sizeof(u64));
+	ALWAYS_ALIGN(sizeof(void*));
 	u64 key;
-};
+} ALIGNED(sizeof(void*));
 
 /*
  * Exported functions and macros.