DataTable Performance

  • Thread starter Thread starter Brian Gideon
  • Start date Start date
B

Brian Gideon

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?
 
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?
Click to expand...

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