Kommt vor allem auch auf die Art des Zugriffs an. Wie Sacaldur schon beschrieben hat, kommt es auf die Art des Problems an, wie man seine Daten strukturiert. Je nach Problem könnte dann eine Linked List, eine List<T> oder auch ein Dictionary Sinn machen.
Multithreading bietet auf Mehrkernprozessoren vorteile, wenn du verschiedene, große Aufgaben hast, die du auf mehrere Kerne verteilen kannst. Nur weil du 4 Kerne hast, läuft die Anwendung aber auch nicht 4 mal so schnell. Außerdem stellt das zusätzliche Anforderungen an deine Klassen und Methoden (Stichwort: Threadsafe).
Wenn du von XML sprichst, würde ich aber sagen, dass hier im Algorithmus das meiste Potential besteht. Die verschiedenen XML Zugriffstechnologien im .NET Framework sind unterschiedlich schnell, haben aber eben auch unterschiedliche Vor- und Nachteile. Vielleicht kannst du uns hier erst einmal mehr Informationen geben, möglichst auch einen Code Ausschnitt.