The Indexing Service and the Windows Search Service (Indexing Service’s replacement) are role services in the File Services role. So you have to install that first.
Which indexing solution should I install?
You should install Windows Search Service, unless you have a customized or non-Microsoft application that requires you to run the legacy Indexing Service on your server. Windows Search Service offers several enhancements over Indexing Service, especially in the areas of extensibility, usability, and performance.