When did David say so?
Rashi: It is while Do'eg was pursuing him.
Why did David compare himself to a fresh olive-tree?
Rashi: I will have sons and grandsons in Beis Hashem.
Radak: Do'eg will wither like a leaf that fell from a tree; it has no hope. I will be like a fresh olive-tree. Its leaves never wither; the entire year, they are fresh and moist.
Malbim: I am rooted in Beis Hashem, unlike Do'eg, who was detained in Beis Hashem, and his root is in a place of Tum'ah. Just like an olive-tree is always fresh and its leaves never wither, so I always trusted in Chesed Elokim.
Why did he say "b'Veis Elokim"?
Radak: Do'eg was detained in Beis Hashem when he had his evil intent. He will be uprooted from Beis Hashem, and I will be like a fresh olive-tree there!
Why did he say "Batachti v'Chesed Elokim"?
Radak: I trusted in Hashem, but Do'eg did not; he trusted in his wealth, and did not fear Hashem.
Malbim: The good that a person gets via his deeds and merits, it is not guaranteed to last always; it can change if his deeds change. The good that comes via Chesed Elokim, not based on his good deeds, is forever, for Chesed Elokim does not change. David received his kingship via Chesed, like I will explain in Perek 89.
