It may likely grow into the Sinapis Nigra (Black Mustard). It can grow to eight feet tall, so it could actually be literally used by small birds to nest on its branches. However parables are not to be taken so literally and the image may be a slight exaggeration as part in parcel with the point of the passage.
In the OT mustard is not mentioned. Yet later Jewish lit. shows that it was well-known in Palestine (Hbr. חַרְדָּל, Aram. חַרְדְּלָא, Arab. chardal), → n. 10. Acc. to the Mishnah (in contrast to → line 10) it was not cultivated in gardens but in fields, Kil., 3, 2; cf. 2, 9. It was grown both for the grains (T. Maas., III, 7 [84]) and also the leaves, loc. cit.; T. Kil., II, 8 [75]). There is no ref. to medical use. The smallness of the seed was proverbial. In some rules of cleanness the slightest quantity defiles, “even as little as a grain of mustard-seed,” Nid., 5, 2; cf. b. Ber., 31a.…to-day the mustard does in fact grow to a height of 2 1/2–3 metres in the vicinity of Lake Gennesaret. (Vol. 7: Theological dictionary of the New Testament. 1964- (G. Kittel, G. W. Bromiley & G. Friedrich, Ed.)
Alfred Edersheim further vindicates that the mustard seed was not a tree but a garden herb that was quite large compared to the small size of its seed. Also that it was proverbial in Jewish culture:
The very idea of Parables implies, not strict scientific accuracy, but popular pictorialness. It is characteristic of them to present vivid sketches that appeal to the popular mind, and exhibit such analogies of higher truths as can be readily perceived by all. Those addressed were not to weigh every detail, either logically or scientifically, but at once to recognise the aptness of the illustration as presented to the popular mind. Thus, as regards the first of these two Parables, the seed of the mustard-plant passed in popular parlance as the smallest of seeds. In fact, the expression, ‘small as a mustard-seed,’ had become proverbial, and was used, not only by our Lord, but frequently by the Rabbis, to indicate the smallest amount, such as the least drop of blood, the least defilement, or the smallest remnant of sun-glow in the sky. ‘But when it is grown, it is greater than the garden-herbs.’ Indeed, it looks no longer like a large garden-herb or shrub, but ‘becomes,’ or rather, appears like, ‘a tree’—as St. Luke puts it, ‘a great tree,’ of course, not in comparison with other trees, but with garden-shrubs. Such growth of the mustard seed was also a fact well known at the time, and, indeed, still observed in the East. (The Life and Times of Jesus the Messiah)
The main point of the parable is that under such small beginnings the kingdom of God in Christ will expand disproportionately to its original 'small' size. History has borne the truthfulness of the parable out quite evidentially.