You should, but B-tree is the most common data structure used for database indexes, and sequential order performs better than random order for index keys.
If one machine can only handle a hundred transactions per second, and you might ever receive more than that, you have to spread the work across several machines, probably by assigning primary keys that aren't (mostly) sequential.
usually in sharding schemes its a few bits of a hash of the id that are used to determine shard; the system or library you are using will take care of this transparently for you.