In cognitive radio (CR) networks, channel rendezvous is a significant operation for two secondary users (SUs) to find a common available channel and establish a link between them. Currently, all previous channel rendezvous designs make the same assumption to ensure that the channel rendezvous process is successful: there must exist at least one common available channel between the SU transmitting pair. However, this assumption is not always feasible. When the number of primary users (PUs) is large, there could be no common available channel between two SUs. This issue results in serious problems in successfully implementing channel rendezvous in CR networks. In this paper, a framework is proposed to tackle this issue by using directional antennas instead of traditionally used omnidirectional antennas. Our proposed framework aims to ensure that the probability that the SU pair have at least one common available channel is larger than a pre-defined threshold. Meanwhile, given a channel rendezvous scheme, the average channel rendezvous delay is minimized. Simulation results show that the proposed framework significantly outperforms the scenario with omni-directional antennas in terms of the probability of successful channel rendezvous when the number of PUs is large. To the best of our knowledge, this is the first paper that utilizes directional antennas to enhance the channel rendezvous performance in CR networks.