DataTable Performance -- dotnet ado.net

Brian Gideon
7/11/2007 7:55:20 AM

I'm interested in knowing the runtime complexity of the DataTable.Find
method in 2.0 when attempting to find a row by the primary key. The
MSDN documentation is vague...probably intentionally. I used .NET
Reflector to examine the DataTable and what I found is that the
primary key index is implemented with a red black tree. That leads to
be believe that the operation is O(log n) unless something else was
going on that I missed. I'm a little disappointed that a O(1)
algorithm isn't used, but I can understand the reasoning behind the
BST since it keeps the index in a sorted order. Can anyone else
confirm?

Brian Gideon
7/11/2007 8:10:09 AM

[quoted text, click to view]

As a follow up I presume calling
DataTable.DefaultView.ApplyDefaultSort = true is O(1) since the
primary key is already sorted?

dotnet ado.net : DataTable Performance