XML : c# update large xml

First I am a complete noob to c#. I Just started learning about 3 weeks ago so if it sounds like I don't know what the heck I'm talking about it's probably because I don't.

The XML:

  <database totalkeys="172" totalvalues="98014">       <key id="k1" name="Key1" valuecount="3">           <value id="v1" name="Value1"/>           <value id="v2" name="Value2"/>           <value id="v3" name="Value3"/>       </key>       <key id="k2" name="Key2" valuecount="3">           <value id="v1" name="Value1"/>           <value id="v2" name="Value2"/>           <value id="v3" name="Value3"/>       </key>  </database>    

The actual XML itself is much larger as you can see by the totalkeys and totalvalues attributes. Each <key> has anywhere from 5 to 19000 values.

In order to update the XML i have to gather info from three separate sources. From these sources I create 3 Dictionaries.

1. Dictonary<string, List<string>> >>> <keyId, List<valueIds>>
2. Dictonary<string, string> >>> <keyId, keyName>
3. Dictonary<string, string> >>> <valueId, valueName>

How do I update the XML without having to individually check if each <key> and <value> already exists? Currently I use SelectSingleNode for each and if it returns null I create the node and append it to the xml. This is very slow. Is there a faster way to go about this? Is XML even the right choice for a database this size?