兵頭と申します。お世話になります。

何だか、とても基本的なことのような気もするのですが、
教えてください。

MSDE2000＋WindowsXPという環境で、VB.NET2003で開発をしています。
例えばA・Bというカラムを持つTableAというテーブルがあったとします。
AはプライマリーキーでNull不許可、BはNull許可です。
TableAにカラムBがNullであるレコードの有無を調べたいような時に、
なるべく早く検索を終える方法はありますでしょうか？
TableAは数十万という件数になる可能性があり、データが増えた
時のパフォーマンスの低下を心配しています。
普通にSelect Count(*) Where 〜などと処理すると、もちろん
全データを検索しますよね？
DBチューニングについてはほとんど経験がないのですが、
カラムBはNullが入ってくる可能性があり、インデックスは
張れないと思います。

それとも、数十万件くらいでは心配するほどのことは
ないのでしょうか？
ちなみに、実際はTableAはカラムが20程度あり、他のカラム
にもインデックスが張られることになると思います。
また、検索処理自体はストアドプロシージャで行う予定です。

環境に左右されることでもあり、ご回答しづらいかと
思いますが、アドバイスをいただければ幸いです。
よろしくお願いいたします。