Как правильно делать поиск по ключу вложенного документа MongoDB?
прямо с $exists: true видимо ничего не получится.
Но можно попробовать извернуться несколькими способами:
1. Добавлять служебное поле, которое и индексировать. Это может еще и хорошо сказаться на размере индекса, особенно если a и b большие, то целицом их индексировать ради $exists расточительно.

2. Если a и b всегда одного типа, можно попробовать использовать такой запрос db.coll.find({'attrib.a': {'$type': 3}})
По крайней мере, если верить explain'у, то индекс он использует.
Не совсем понятна суть вопроса, если имеется в виду получение всех документов содержащих attrib.a. Тогда можно использовать разряженные индексы:

> db.ttt.find(); // документы коллекции
{ "_id" : ObjectId("50377f098537d96af9ea28ae"), "attrib" : { "a" : { }, "b" : { } } }
{ "_id" : ObjectId("50377f0c8537d96af9ea28af"), "attrib" : { "b" : { } } }
{ "_id" : ObjectId("50377f0f8537d96af9ea28b0"), "attrib" : { "a" : { } } }
{ "_id" : ObjectId("50377f138537d96af9ea28b1"), "attrib" : { } }

> db.ttt.ensureIndex({'attrib.a':1}, {sparse : true}); // разряженный индекс
> db.ttt.find().sort({'attrib.a':1}); // в результате будут только документы содержащие attrib.a
{ "_id" : ObjectId("50377f0f8537d96af9ea28b0"), "attrib" : { "a" : { } } }
{ "_id" : ObjectId("50377f098537d96af9ea28ae"), "attrib" : { "a" : { }, "b" : { } } }

> db.ttt.find().hint({'attrib.a':1}); // явно указан индекс
{ "_id" : ObjectId("50377f0f8537d96af9ea28b0"), "attrib" : { "a" : { } } }
{ "_id" : ObjectId("50377f098537d96af9ea28ae"), "attrib" : { "a" : { }, "b" : { } } }

Сразу можно документы с определенным значением attrib.a отбирать. Если необходимо проверять наличие объектов в определенном документе, тогда такой вариант скорее всего не подойдет.