diff --git a/ebtree/eb32sctree.h b/ebtree/eb32sctree.h
index f547ff0..7061308 100644
--- a/ebtree/eb32sctree.h
+++ b/ebtree/eb32sctree.h
@@ -38,13 +38,18 @@
  * 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(long), we know there will be some padding after
+ * the leaf 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 eb32sc_node {
 	struct eb_node node; /* the tree node, must be at the beginning */
+	MAYBE_ALIGN(sizeof(u32));
 	u32 key;
+	ALWAYS_ALIGN(sizeof(void*));
 	unsigned long node_s; /* visibility of this node's branches */
 	unsigned long leaf_s; /* visibility of this node's leaf */
-};
+} ALIGNED(sizeof(void*));
 
 /*
  * Exported functions and macros.
diff --git a/ebtree/eb32tree.h b/ebtree/eb32tree.h
index 8c1a470..3896fb8 100644
--- a/ebtree/eb32tree.h
+++ b/ebtree/eb32tree.h
@@ -41,8 +41,9 @@
  */
 struct eb32_node {
 	struct eb_node node; /* the tree node, must be at the beginning */
+	MAYBE_ALIGN(sizeof(u32));
 	u32 key;
-};
+} ALIGNED(sizeof(void*));
 
 /*
  * Exported functions and macros.
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.
diff --git a/ebtree/ebmbtree.h b/ebtree/ebmbtree.h
index 3200a12..8262ec6 100644
--- a/ebtree/ebmbtree.h
+++ b/ebtree/ebmbtree.h
@@ -36,11 +36,16 @@
  * is, the end user is not meant to manipulate internals, so this is pointless.
  * The 'node.bit' value here works differently from scalar types, as it contains
  * the number of identical bits between the two branches.
+ * Note that we take a great care of making sure the key is located exactly at
+ * the end of the struct even if that involves holes before it, so that it
+ * always aliases any external key a user would append after. This is why the
+ * key uses the same alignment as the struct.
  */
 struct ebmb_node {
 	struct eb_node node; /* the tree node, must be at the beginning */
+	ALWAYS_ALIGN(sizeof(void*));
 	unsigned char key[0]; /* the key, its size depends on the application */
-};
+} ALIGNED(sizeof(void*));
 
 /*
  * Exported functions and macros.
diff --git a/ebtree/ebpttree.h b/ebtree/ebpttree.h
index a1db03b..6cd6659 100644
--- a/ebtree/ebpttree.h
+++ b/ebtree/ebpttree.h
@@ -44,11 +44,14 @@
  * 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.
  * Internally, it is automatically cast as an eb32_node or eb64_node.
+ * We always align the key since the struct itself will be padded to the same
+ * size anyway.
  */
 struct ebpt_node {
 	struct eb_node node; /* the tree node, must be at the beginning */
+	ALWAYS_ALIGN(sizeof(void*));
 	void *key;
-};
+} ALIGNED(sizeof(void*));
 
 /*
  * Exported functions and macros.
diff --git a/ebtree/ebtree.h b/ebtree/ebtree.h
index e87e961..dff044b 100644
--- a/ebtree/ebtree.h
+++ b/ebtree/ebtree.h
@@ -379,11 +379,7 @@
 	eb_troot_t    *leaf_p;  /* leaf node's parent */
 	short int      bit;     /* link's bit position. */
 	short unsigned int pfx; /* data prefix length, always related to leaf */
-}
-#ifdef HA_UNALIGNED
-   __attribute__((packed))
-#endif
-   ;
+} __attribute__((packed));
 
 /* Return the structure of type <type> whose member <member> points to <ptr> */
 #define eb_entry(ptr, type, member) container_of(ptr, type, member)