All this question pertain to MS sql.
Every table should be indexed with more than one index. The only downside of indexing a table is that updates and inserts are a bit slower because more structures have to be maintained, but unless we are doing hundreds of updates/inserts per second, you will not notice any performance impact on your application.
How does an index work?
To know how does an index work, you first have to see how the data is stored in sql. In sql the data is store in a file, by tables /row. This means that all the information for one table is placed sequentially on the file, ordered by the CLUSTERED INDEX. This means the Clustered Index gives you a sequence of data.
For example the table
Customer_ID , Customer_Name
1 Alex
2 Michael
3 Kevin
4 Smith
5 John
6 Peter
7 Zen
This will be on the file as 1 Alex, 2 Michael, 3 Kevin, 4 Smith, 5 John, 6 Peter, 7 Zen
If we create a NON clustered index on Customer name the tree structure will look like
Now look at the query
Select * from Customer where Customer_Name = 'Peter'
If you only have a clustered index, Sql has to look at the whole table in order to find the records that match the where clause. This is called a table scan, and is extremely expensive, reason been is that sql has to transverse the whole table every time.
Check it out on the clustered index sql has to load record 1 and compare Alex with Peter, no good, next row, Alex with Michael, no good, next row; even if it gets to row 6, and find it, it still have to keep going and load record 7 and compare Zen with Alex. This is because more than one row can match your where clause. Btw every record that gets compared is a logical read, so we are doing for this table 6 logical reads for every time we want to find a record by the customer name
Now with the NON clustered index
Sql start at the first node (Michael) and compares Michael with Peter, comparison negative, then goes to the node with the proper direction, peter is to the right, so it ignores everything to the left of the node "michael". In other words Sql will ignore nodes kevin Alex and John. Sql loads next node Peter and finds a match, not only it finds a match but it doesn't need to go further down as duplicate record will appear at the same node level.
So how many logical reads is that, for michael it was just 2 reads. And you can guarantee that the amount of reads is exponentially smaller and it is related logarithmically to the table size. This mean the table can be in the millions of row, but the level of the index can be in the hundreds. This search process called a index Seek and it is what you should strive for.
On the picture i used a Binary tree that only has two branches, sql uses a B tree structure that has more than 2 nodes per level, increasing the efficiency
TLDR, yes add indexes on every table after looking at the queries that are run against it.
For the other question are you asking froma code perpective or sql perpective. The word DAtaset is a programming word, and a dataset should be avoided. It is very verr inefficient compare to Sql readers.
