diff --git a/source/lib/registry/ldb.c b/source/lib/registry/ldb.c
index 28cfe66..3e98d2f 100644
--- a/source/lib/registry/ldb.c
+++ b/source/lib/registry/ldb.c
@@ -207,6 +207,9 @@ static WERROR cache_subkeys(struct ldb_key_data *kd)
 	}
 
 	kd->subkey_count = res->count;
+	/* If re-building the cache, clear out old values */
+	if (kd->subkeys)
+		talloc_free(kd->subkeys);
 	kd->subkeys = talloc_steal(kd, res->msgs);
 	talloc_free(res);
 
@@ -228,6 +231,9 @@ static WERROR cache_values(struct ldb_key_data *kd)
 		return WERR_FOOBAR;
 	}
 	kd->value_count = res->count;
+	/* If re-building the cache, clear out old values */
+	if (kd->values)
+		talloc_free(kd->values);
 	kd->values = talloc_steal(kd, res->msgs);
 	talloc_free(res);
 	return WERR_OK;
@@ -346,6 +352,10 @@ static WERROR ldb_open_key(TALLOC_CTX *mem_ctx, const struct hive_key *h,
 	newkd->ldb = talloc_reference(newkd, kd->ldb);
 	newkd->dn = ldb_dn_copy(mem_ctx, res->msgs[0]->dn);
 
+	/* Create the caches */
+	cache_subkeys(newkd);
+	cache_values(newkd);
+
 	*key = (struct hive_key *)newkd;
 
 	talloc_free(res);
@@ -430,6 +440,9 @@ static WERROR ldb_add_key(TALLOC_CTX *mem_ctx, const struct hive_key *parent,
 
 	*newkey = (struct hive_key *)newkd;
 
+	/* Update the cache */
+	cache_subkeys(discard_const_p(struct ldb_key_data, parentkd));
+
 	return WERR_OK;
 }
 
@@ -453,6 +466,9 @@ static WERROR ldb_del_key(const struct hive_key *key, const char *name)
 		return WERR_FOOBAR;
 	}
 
+	/* Update the cache */
+	cache_subkeys(parentkd);
+
 	return WERR_OK;
 }
 
@@ -481,6 +497,9 @@ static WERROR ldb_del_value (struct hive_key *key, const char *child)
 		return WERR_FOOBAR;
 	}
 
+	/* Update the cache */
+	cache_values(kd);
+
 	return WERR_OK;
 }
 
@@ -517,6 +536,10 @@ static WERROR ldb_set_value(struct hive_key *parent,
 	}
 
 	talloc_free(mem_ctx);
+
+	/* Update the cache */
+	cache_values(kd);
+
 	return WERR_OK;
 }