Indexing is related to searching. The core has a way of indexing posts, mainly, by means of the ^words table. So when you search you search for exact matches in that table.
You might not like the way the indexing works and you might want to be able to search for partial matches such as "question2an*" and expect that to match "question2answer". Current core's indexing way will not allow you to do so.
Now there is module type called search. This module will allow you to plug your own way of searching into the core, and even fully replace it. As I said before, indexing is related to searching. If you want to perform an efficient text search that handles the wildcard I mentioned before, just searching in the current data, although possible, won't be efficient at all.
So you need to structure data in a very different way. You could create additional tables, use lucene indexes, Solr, or whatever you want. The thing is, that although you might have all the additional infrastructure and even a way of replacing the core's way of searching you still need to add and remove the data into your custom search system.
That is what indexing and unindexing functions do. The indexing adds something when it changes, for instance, when you create or edit a question. The unindexing removes them from the index, for instance, when you delete a post. This works this way because you need to keep the index up-to-date with the actual data in Q2A. If you don't you might get results in your custom search system that no longer exists or miss results that exists in the actual core tables but are not part of your custom search system.
1) Your first GitHub link is the function that calls all plugins that implement a search module. Your second link is how the core calls those plugins (that is very low level). You shouldn't care much about those functions and focus in the search modules which are the ones you can actually implement from a plugin developer perspective.
2) Many people have asked questions about adding new post types. I have answered myself some of them sometime ago and added in one of them a detailed explanation about different approaches and their pros and cons. I couldn't find that question after searching for it. In short, you can add new post types to the ^posts table. This won't interfere with the core.
However, you need to understand that the core will almost not see them. This even means that you won't see the in the question lists at all. In order to list them you would need to create custom pages and also add your own data access functions. Another very related issue was the operations you can perform on those new post types. If you want votes or the ability to select answers on them then this will add a lot of work. Best approach would be to see how they work on current post types and try to adapt them to your own post types.
Now, if you don't care about making them fit into current existing post rules (like the ability to vote them) then it will be considerably easier. You could even create your own voting mechanism totally separated from the core. Any scenario means a lot of work :(
